[LintCode] 3 Sum
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 32 33 34 |
public ArrayList<ArrayList<Integer>> threeSum(int[] numbers) { // write your code here ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); if(numbers.length == 0 || numbers == null) return res; Arrays.sort(numbers); for(int i = 0 ; i < numbers.length - 2; i++) { if(i != 0 && numbers[i] == numbers[i-1]) continue; int l = i+1; int r = numbers.length - 1; while(l < r){ int sum = numbers[i] + numbers[l] + numbers[r]; if(sum == 0){ ArrayList<Integer> tmp = new ArrayList<Integer>(); tmp.add(numbers[i]); tmp.add(numbers[l]); tmp.add(numbers[r]); res.add(tmp); l++; r--; while(l < r && numbers[l] == numbers[l-1]) l++; while(l < r && numbers[r] == numbers[r+1]) r--; }else if(sum > 0) r--; else l++; } } return res; } |
Leave A Comment