LeetCode_15: 3Sum

# 引言

题目链接：https://leetcode.com/problems/3sum/description/

# 题目大意

给出一个包含n个整数的数组nums, 这个数组是否存在元素有a,b,c使得a + b + c = 0, 找出所有满足条件的a,b,c的组合

• Example

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

# 题解

很容易想到暴力解法, 三重循环穷举所有可能进行判断, 但很明显这种方法会超时, 想一想有什么办法能够优化不必要的循环？

排序？

将数组排序, 从起始点进行大小长度为三的滚动判断即可, 这样就好像省去了两重循环, 事件复杂度变成了 O(3*n)?

由于数字可能为负数, 所以选取当前有序数组两端的数字更可能构成目标数字零, 所以数字的滚动不应该选取连续的。

选择一个标志点作为第一个数字从零开始往后推进, 从当前标志位往后剩余数组两端选取剩余两个目标数字进行判断, 并不断往中间压缩判断即可(由于数组有序, 剩余两个数在当前位置之后寻找, 只要第一个数字不断推进直到结束, 过程中可以覆盖所有解)

具体压缩判断条件如下：

每次根据当前选取三个数字的和和目标值0比较, 大于目标值0, 第三个数字从剩余数组从后往前选取, 小于目标值0, 第二个数字从剩余数组从前往后选取, 每次选定三个目标值后将数字的和和目标值0比较, 满足条件存储即可

int midIndex = i + 1;
int lastIndex = len - 1;
int curSum = nums[i] + nums[midIndex] + nums[lastIndex];

if (curSum > 0) --lastIndex;
if (curSum < 0) ++midIndex;

# 复杂度

时间复杂度 O(n^2)

空间复杂度 O(1)

# AC代码

c++版本

class Solution
{
  public:
    vector<vector<int>> threeSum(vector<int> &nums)
    {
        vector<vector<int>> retAns;
        std::sort(nums.begin(), nums.end());
        const int len = nums.size();
        for (int i = 0; i < len - 2; ++i)
        {
            if (nums[i] > 0)
            {
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1])
            {
                continue;
            }
            int midIndex = i + 1;
            int lastIndex = len - 1;
            while (midIndex < lastIndex)
            {
                int curSum = nums[i] + nums[midIndex] + nums[lastIndex];
                if (curSum == 0)
                {
                    retAns.push_back({nums[i], nums[midIndex++], nums[lastIndex--]});
                    while (midIndex < lastIndex && nums[midIndex] == nums[midIndex - 1])
                    {
                        ++midIndex;
                    }
                    while (midIndex < lastIndex && nums[lastIndex] == nums[lastIndex + 1])
                    {
                        --lastIndex;
                    }
                }
                else if (curSum > 0)
                {
                    --lastIndex;
                }
                else
                {
                    ++midIndex;
                }
            }
        }
        return retAns;
    }
};

go版本

func threeSum(nums []int) [][]int {
	var retAns [][]int
	lens := len(nums)
	sort.Sort(sort.IntSlice(nums))
	for i := 0; i < lens-2; i++ {
		if nums[i] > 0 {
			break
		}
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		midIndex, lastIndex := i+1, lens-1
		for midIndex < lastIndex {
			curSum := nums[i] + nums[midIndex] + nums[lastIndex]
			if curSum == 0 {
				retAns = append(retAns, []int{nums[i], nums[midIndex], nums[lastIndex]})
				midIndex++
				for midIndex < lastIndex && nums[midIndex] == nums[midIndex-1] {
					midIndex++
				}
				lastIndex--
				for midIndex < lastIndex && nums[lastIndex] == nums[lastIndex+1] {
					lastIndex--
				}
			} else if curSum > 0 {
				lastIndex--
			} else {
				midIndex++
			}
		}
	}
	return retAns
}