leetcode: 3Sum

1. 题目描述

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] 
such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.

Example1

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

Constraints:

• 3 <= nums.length <= 3000
• 105 <= nums[i] <= 105

2. 思考

  在做该题之前，建议对Two Sum和leetcode: Two Sum II - Input Array is Sorted，这两道题目先进行了解。
  Two Sum问题的最优时间复杂度为$o(n)$，因此对于3Sum问题应该来讲较容易的写出时间复杂度为$o(n^2)$的解法。但该题目的难点在于triplet要找出所有的方案，同时要去重。
  首先，由于当前预设的时间复杂度为$o(n^2)$，因此可以先对array进行排序，这样不会改变时间复杂度的量级，同时有利于下面的去重操作。
  首先对于外层循环，我们仅对首次遇到的元素进行进一步的内层循环。如何理解这句话：

  假如当前外层循环，进行到红色区域段。对于第一个-7, 可以将其之后的数组$S$进行内层循环，找出和为7的两个元素的所有不重复方案。找到的方案熟练假设为$n$。
  假设想对非首次遇到的元素进行进一步的内层循环，假设找到的方案假设为$n^{{}^{\prime }}$，此时是不可以的，会导致最终重复的解决方案。

  因为$S^{{}^{\prime }}\subset S$，而两者的目标都是一致：寻找到和为7的元素。必然会导致$n^{{}^{\prime }}\subset n$。也即方案的重复，因此对于外层循环，我们仅对首次遇到的元素进行进一步的内层循环。
  对于内层循环，与之类似，也是通过跳过重复的元素来，防止方案重复。

3. 解题

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(), nums.end());vector<vector<int>> res;for(int i = 0; i < nums.size(); ++i){if(0 == i || nums[i - 1] != nums[i]){twoSum(nums, i, res);}}return res;}
private:void twoSum(vector<int>& nums, int i, vector<vector<int>> &res){int left = i + 1, right = nums.size() - 1;while(left < right){int sum = nums[i] + nums[left] + nums[right];if(sum < 0){++left;}else if (sum > 0){--right;}else{res.push_back({nums[i], nums[left++], nums[right--]});while(left < right && nums[left - 1] == nums[left])++left;}} }
};

  其中，保证了，若以nums[i]为开始(3元素方案)，则后续的方案不会重复。

 if(0 == i || nums[i - 1] != nums[i]){twoSum(nums, i, res);

  该段代码，保证了若以nums[left]为开始(2元素方案)，则后续的方案不会重复。

        while(left < right && nums[left - 1] == nums[left])++left;

3. 总结

  该题相对较难，尤其是消除重复方案这部分，最好以类似于动态规划的思想（假设子问题已解决）来理解。在一定理解的基础上进行记忆。