LeetCode [15] 3Sum

15. 3Sum

Medium

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

Notice that the solution set must not contain duplicate triplets.

 

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Example 2:

Input: nums = []
Output: []

Example 3:

Input: nums = [0]
Output: []

 

Constraints:

• 0 <= nums.length <= 3000
• -105 <= nums[i] <= 105

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

class Solution{ public: bool sum3(vector<int> nums, int target){ int n = nums.size(); sort(nums.begin(), nums.end()); // PrintVector(nums, "nums"); return bfs(n, 0, vector<int>(), target, nums); } bool bfs(int n, int pos, vector<int> vec, int target, vector<int> &nums){ int s = accumulate(vec.begin(), vec.end(), 0); int sz = vec.size(); if(sz==3 && s==target){ // PrintVector(vec, "ret"); return true; } if(sz<3 && pos<n){ if(s>=target && nums[pos]>0) return false; if(bfs(n, pos+1, vec, target, nums)) return true; vec.push_back(nums[pos]); if(bfs(n, pos, vec, target, nums)) return true; } return false; } };

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

class Solution { public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); int n = nums.length; List<List<Integer>> ret = new ArrayList<>(); for(int i=0; i<n; ++i){ if(nums[i]>0) break; if(i>0 && nums[i]==nums[i-1]) continue; int l = i+1, r = n-1; while(l<r){ if(l>i+1 && nums[l]==nums[l-1]){ l++; continue; } int s = nums[i] + nums[l] + nums[r]; if(s<0){ l++; }else if(s>0){ r--; }else{ ret.add(Arrays.asList(nums[i], nums[l], nums[r])); l++; r--; } } } return ret; } }