题目: 三数之和

来自智得网
跳转至： 导航、​ 搜索

分析

三数之和可以可以拆解为一个数字和两个数字之和的和，也就是，所以三数之和可以转换为两数之和的问题。

暴力破解

因为是求解三数之和，所以暴力破解法需要三层循环，三层循环可以遍历出来集合中所有的三元组，然后计算所有三元组的和，因为答案是需要返回所有符合结果的三元组，所以如果三元组的值为0，则存储这个三元组。

使用了三层循环，所以暴力破解法的时间复杂度是Θ（n3）。

因为题目要求返回不重复的值，所以需要对结果进行去重。 R 去重可以通过比对所有符合结果的三元组的值来进行去重，但是常规的去重需要两两比对来判断是否重复，两两比对过程时间复杂度也是Θ（n2）。

去重可以通过Hash表的方式进行去重，三元组可以通过排序来确定唯一的序列，将排序之后的序列存储在Hash表。当有新的三元组符合条件的时候判断该值是否已经存在来进行去重，通过Hash表的方式去重，每个结果只需要判读一次，所以时间复杂度是Θ（n）。

双指针

首先将数组排序。

轮询数组的每个数字，假如为an，然后求解数组中是否存在两个数字等于-an，就可以使用双指针的方式来求解，定义两个指针分别指向数组的头尾部。计算头尾指针指向的两个数字的和是否等于-an，如果相等则求得一组三元组的解，如果该值大于-an，则将尾部指针左移，否则将头部指针右移。

因为是求数组中所有符合条件的值，所以求的一组解之后，仍然需要继续移动指针，直到左右指针发生重合位置。

因为双指针法过程中三元组是已经排序的，所以去重的过程可以使用Hash表的方式进行。

双指针过程中排序的时间复杂度是，计算三数之和的时间复杂度是Θ（n2），所以整体的时间复杂度是Θ（n2）。

Hash法

三数之和可以转换为两数之和，遍历集合中的每个数字，例如位置为i的数字值为ai，那么根据题意，问题就转换为了查找剩余集合（除了位置i之外）中是否存在两数之和是-ai的问题。

  • 外层遍历每个数字，假如当前位置为i，数字为ai。
  • 内存遍历除了位置i的数字，查找两数之和为-ai的两个数。
  • 三元组去重。

因为两数之和的时间复杂度是O（n），三数之和多了一层循环，所以时间复杂度是O（n2）

解题

暴力破解

代码如下： 

func Solution(nums []int) [][3]int {

	distinctHashTable := make(map[[3]int][3]int)
	for m := 0; m < len(nums)-1; m++ {
		for n := m + 1; n < len(nums); n++ {
			for k := n + 1; k < len(nums); k++ {
				if nums[m]+nums[n]+nums[k] == 0 {
					sortedNums := threeNumSort(nums[m], nums[n], nums[k])
					distinctHashTable[sortedNums] = sortedNums
				}
			}
		}
	}

	var result [][3]int
	for k, _ := range distinctHashTable {
		result = append(result, k)
	}

	return result
}

func threeNumSort(first int, second int, third int) [3]int {
	nums := [3]int{first, second, third}
	return threeNumArraySort(nums)
}

func threeNumArraySort(nums [3]int) [3]int {
	min := nums[0]
	max := nums[1]
	var mid int
	if nums[0] > nums[1] {
		min = nums[1]
		max = nums[0]
	}

	if nums[2] < min {
		mid = min
		min = nums[2]
	} else if nums[2] > max {
		mid = max
		max = nums[2]
	} else {
		mid = nums[2]
	}

	result := [3]int{min, mid, max}
	return result
}

Hash法

代码如下：

双指针法

代码如下： 

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        // 找出a + b + c = 0
        // a = nums[i], b = nums[left], c = nums[right]
        for (int i = 0; i < nums.size(); i++) {
            // 排序之后最小元素已经大于零，显然没有符合要求的三元组，直接返回
            if (nums[i] > 0) {
                return result;
            }
           
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = nums.size() - 1;
            while (right > left) {
                if (nums[i] + nums[left] + nums[right] > 0) {
                    right--;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                } else if (nums[i] + nums[left] + nums[right] < 0) {
                    left++;
                    while (left < right && nums[left] == nums[left - 1]) left++;
                } else {
                    result.push_back(vector<int>{nums[i], nums[left], nums[right]});
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;

                    right--;
                    left++;
                }
            }

        }
        return result;
    }
};
取自“https://www.aigetting.com/index.php?title=题目:三数之和&oldid=2106”