15. 3Sum

发表于 | 分类于 | 阅读次数
字数统计 1,003 | 阅读时长 5

15. 3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

1
2
3
4
5
6
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
  [
    [-1, 0, 1],
    [-1, -1, 2]
  ]

题意：

　　给一个含有n个整数的S数组，是否有三元组a,b,c在S中使a + b + c = 0，在S中找到所有的不重复的三元组，当三元组的和为0的时候。

注意：

　　结果集不能包含重复的三元组。

思路：

　　这道题的思路和Two Sum差不多，简单方式是暴力查找，先排序，然后3层循环遍历数组，时间复杂度O(n3)。优化时，可以先固定一个数，再用两个指针l和r从这个数后面的两边往中间查找，当这三个数之和等于0的时候，记录一下，当之和大于0的时候，r左移，而当之和小于0的时候，l右移，直到l和r相遇。这个其实就是在Two Sum外层加1层循环，因此时间复杂度是排序的O(nlogn)加O(n2)，即O(n2)。
　　由于三个数字需要按照非递减序列排放，因此先排序可以满足此要求。又要求不包含重复元素，因此在选择第一个数字的时候以及后面两个指针查找时，需要跳过重复元素

　　具体步骤：

  1. 先升序排序，然后用第一重for循环确定第一个数字。
  2. 然后在第二重循环里，第二、第三个数字分别从两端往中间扫。
  3. 如果三个数的sum等于0，得到一组解。
  4. 如果三个数的sum小于0，说明需要增大，所以第二个数往右移。
  5. 如果三个数的sum大于0，说明需要减小，所以第三个数往左移。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
	vector<vector<int>> threeSum(vector<int>& nums) {
		vector<vector<int>> res;
		set<vector<int>> tempRes;//set集合也是为了防止出现重复元素
		if (nums.size() < 3)
			return res;
		sort(nums.begin(), nums.end());
		for (int i = 0; i < nums.size() - 2; i++)
		{
			if (nums[i] > 0)//第i个大于0，后面的数一定大于零，按数组递增排序
				break;
			if (i>0 && nums[i] == nums[i - 1])//排序后如果nums[i] == nums[i - 1]，肯定会出现和前一个i重复的三元组
              continue;
			int pre = i + 1;
			int tail = nums.size() - 1;
			while (pre<tail)
			{
				vector<int> vals;
				int sum = nums[i] + nums[pre] + nums[tail];
				if (sum == 0)
				{
					vals.push_back(nums[i]);
					vals.push_back(nums[pre]);
					vals.push_back(nums[tail]);
					tempRes.insert(vals);
					pre++;
					tail--;
					while (pre < tail&&nums[pre] == nums[pre - 1])
                      				pre++;//因为同一个nums[i]，如果nums[pre] == nums[pre - 1],则取出来的三元组肯定是重复的，所以直接把pre向后移动，然后再计算
					while (pre < tail&&nums[tail] == nums[tail + 1])
                      				tail--;//因为一个nums[i]，如果nums[tail] == nums[tail + 1],则取出来的三元组肯定是重复的，所以直接把tail向前移动，然后再计算
				}
				else if (sum < 0)
				{
					pre++;
				}
				else
					tail--;
			}

		}
		for (auto s : tempRes)
		{
			res.push_back(s);
		}
		return res;
	}
};

　Java Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        if (null == nums) {
            return new ArrayList();
        }
        int len = nums.length;
        if (len == 0) {
            return new ArrayList();
        }

        Set<List<Integer>> res = new HashSet();
        Arrays.sort(nums);

        for (int i = 0;i < len - 2;i++) {
            int curNum = nums[i];
            if (curNum > 0) {
                break;
            }

            if (i > 0 && curNum == nums[i - 1]) {
                continue;
            }
            int pre = i + 1;
            int tail = len - 1;
            while (pre < tail) {
                List<Integer> zeroNums = new ArrayList();
                int preNum = nums[pre];
                int tailNum = nums[tail];
                int sum = curNum + preNum + tailNum;
                if (sum == 0) {
                    zeroNums.add(curNum);
                    zeroNums.add(preNum);
                    zeroNums.add(tailNum);
                    res.add(zeroNums);
                    pre++;
                    tail--;

                    while (pre < tail && nums[pre] == nums[pre - 1]) {
                        pre++;
                    }
                    while (pre < tail && nums[tail] == nums[tail + 1]) {
                        tail--;
                    }
                } else if (sum > 0) {
                    tail--;
                } else {
                    pre++;
                }
            }
        }
        return res.stream().collect(Collectors.toList());
    }
}