# 引言

题目链接: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
}
更新于 阅读次数

请我喝[茶]~( ̄▽ ̄)~*

yx.zhang 微信支付

微信支付

yx.zhang 支付宝

支付宝