O(n^2) solution using two pointers and sort, easy to understand


  • 0
    K
    public class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> l = new ArrayList<List<Integer>>();
            if (nums == null || nums.length < 3) {
                return l;
            }
            
            Arrays.sort(nums); // sort and then use problem --> Two Sum 2
            
            for (int i = 0; i< nums.length -2 ; i++) {
                int first = nums[i]; // --> only when first is same --> target is same --> duplicate produce here
                int target = nums[i] * (-1);
                
                int left = i+1;
                int right = nums.length -1;
                while(left < right) { // can not count it self twice
                    int sum = nums[left] + nums[right];
                    if (sum < target) {
                        left ++;
                    }else if (sum > target) {
                        right --;
                    }else {
                        List<Integer> ll = new ArrayList<Integer>();
                        ll.add(first);
                        ll.add(nums[left]);
                        ll.add(nums[right]);
                        l.add(ll);
                        // avoid dups --> if this is already use --> not need to keep it
                        while ((left < nums.length -1) && (nums[left + 1] == nums[left])){ // only need to update one part because A + B == TARGET IF A change B is same A1 + B not equal to target
                            left = left + 1;
                        }
                        left++;
                    }
                } 
                while ((i < nums.length -1)&& (nums[i+1] == first)) {
                    i++;
                } // after next i ++ --> we will get the number which is not first
            }
            return l;
        }
    }
    

    Problem which is better to do before this
    https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.