https://neetcode.io/problems/three-integer-sum?list=neetcode150
initial
so i didnt know how at all. First we cannot have duplicate combis so once we find a valid case we should skip the duplicates.
We realise that nums[i]+nums[j]+nums[k]=0. So if we fix nums[i], we get a 2 sum problem. We need a sorted list to get the sum of nums[j] and nums[k] as a pattern. And once we find valid case we shift left and right pointer to not have duplicate values as that previous values.
sol
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int n = nums.length;
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(nums);
for(int i=0; i<n-2;i++){
int left=i+1,right=n-1;
if(i>0 && nums[i-1]==nums[i]) continue;
while(left<right){
int sum = nums[left]+nums[right]+nums[i];
if(sum==0){
// List<Integer> tmp = new ArrayList<>();
// tmp.add(nums[i]);
// tmp.add(nums[left]);
// tmp.add(nums[right]);
// ans.add(new ArrayList<>(tmp));
ans.add(Arrays.asList(nums[i],nums[left],nums[right]));
while(left+1<n && nums[left+1]==nums[left]) left+=1;
while(right-1>=left && nums[right]==nums[right-1]) right-=1;
left+=1;
right-=1;
} else if(sum<0) left+=1;
else right-=1;
}
}
return ans;
}
}
complexity
is it n log n time and n space
no
sorting is n log n but the outer loop is n but the inner loop(2 sum) is also o(n) in worst case so n^2. so it is n^2.
its 1 space
