s= [-1,0,1,2,-1,-4] and target is 0
A solution set is:
(-1,0,1)
(-1,-1,2)
2. Implementation
Thought1:
Q1: like two Sum
A1: sort the array first
Fix one and the rest use twoSum()
Q1: fix one which one
A1: from the end of the array
Q1: Duplicate solution avoid
A1: same element not being used twice, num[i] in fix one, and the other two in twoSum
Q1: how to combine twoSum and fixed one element to become three sum
A1: list get and add and addAll
FOLLOW UP: solution element in order as original array?
List
public List3. Similar Ones> threeSum (int[] num) { List
> res = new ArrayList
>(); // valid the input if (num == null || num.length <3 data-blogger-escaped--1="" data-blogger-escaped-arrays.sort="" data-blogger-escaped-for="" data-blogger-escaped-i="" data-blogger-escaped-int="" data-blogger-escaped-note:="" data-blogger-escaped-num="" data-blogger-escaped-res="" data-blogger-escaped-return="" data-blogger-escaped-sort="">1 ; i--) { // NOTE: avoid repeated solution if ( i == num.length || num[i] != num[i+1] ) { List
> curRes = twoSum(num, i-1, 0 - num[i]); for (int j = 0 ; j < curRes.size();j++) { curRes.get(j).add(num[i]); } res.addAll(curRes); } } return res; } private List
> twoSum (int[] num, int end, int target) { List
> res = new ArrayList
>(); //validate the input if ( nums == null || nums.length < 2) { return res; } int l =0 ; int r = end; while (l< r) { if ( num[l] + num[r] == target ) { List
item = new ArrayList (); item.add(num[l]); item.add(num[r]); // NOTE: no need to check repeated solution since already avoid when iterating res.add(item); // NOTE: more than one solution so iterating l++; r--; // avoid Duplicate solution while (l < r && num[l] == num[l-1] ) { l++; } while( l< r && num[r] == num[r+1] ) { r--; } } else if ( num[l] + num[r] > target ) { r--; } else { l++ } // NOTE : avoid solution when equal to target } return res; }
Combination Sum II
Two Sum
4Sum
3Sum closest
No comments:
Post a Comment