O(n^2) Java solution with bound optimization


  • 0
    Z

    The main idea is get target number in a sorted array

    1. sort the input array
    2. set left index to be 0, right index to be nums.length -1
    3. calculate the target number(0-nums[left]-nums[right])
    4. search the target number in sorted array

    The AC code

        public List<List<Integer>> threeSum(int[] nums) {
    
            Arrays.sort(nums);
    
            List<List<Integer>> result = new ArrayList<>();
    
            if (nums == null || nums.length < 3) {
                return result;
            }
    
            for(int left = 0; left< nums.length && nums[left] <= 0; ) { //left loop to first 0
                boolean flag = true;
                for(int right = nums.length - 1; flag && right> 0 && nums[right] >= 0;) {//right loop to last 0
                    int curr = 0 - nums[left] - nums[right]; // target number
                    if (right > 0 && nums[right - 1] < curr) { //no need to search, break the right loop
                        flag = false;
                        continue;
                    }
                    int k = 0; // target number index
                    if(curr< 0) { //search from left to right
                        k = left;
                        while (++k < right && nums[k] < curr) ;
    
                    } else { //search target from right to left
                        k = right;
                        while (--k > left && nums[k] > curr) ;
                    }
                    if(k>left && k < right && nums[k] == curr) { //bingo
                        List<Integer> added = new ArrayList<>();
                        added.add(nums[left]);
                        added.add(nums[right]);
                        added.add(curr);
                        result.add(added);
                    }
                    int iRight = right;
                    while(--right >= 0 && nums[right] == nums[iRight]) ; //skip duplicated numbers
                }
                int index = left;
                if(nums[left] >= 0) break; //break when we met first 0, time optimization
                while(++left < nums.length && nums[left] == nums[index]) ; //skip duplicated numbers
            }
            return result;
        }
    

  • 0
    Z

    I just thought maybe i can use binary-search to get the target number, and it works

        public List<List<Integer>> threeSum(int[] nums) {
    
            Arrays.sort(nums);
    
            List<List<Integer>> result = new ArrayList<>();
    
            if (nums == null || nums.length < 3) {
                return result;
            }
    
            for(int left = 0; left< nums.length && nums[left] <= 0; ) { //left loop to first 0
                boolean flag = true;
                for(int right = nums.length - 1; flag && right> 0 && nums[right] >= 0;) {//right loop to first 0
                    int curr = 0 - nums[left] - nums[right]; // target number
                    if (right > 0 && nums[right - 1] < curr) { //no need to search, break the right loop
                        flag = false;
                        continue;
                    }
                    int k = biSearch(nums, curr, left+1, right-1); //biSearch target number index
                    if(k>0 && nums[k] == curr) { //bingo
                        List<Integer> added = new ArrayList<>();
                        added.add(nums[left]);
                        added.add(nums[right]);
                        added.add(curr);
                        result.add(added);
                    }
                    int iRight = right;
                    while(--right >= 0 && nums[right] == nums[iRight]) ; //skip duplicated numbers
                }
                int index = left;
                if(nums[left] >= 0) break; //break when we met first 0, time optimization
                while(++left < nums.length && nums[left] == nums[index]) ; //skip duplicated numbers
            }
            return result;
        }
    
        private int biSearch(int[] array, int target, int left, int right) {
    
            while(left <= right) {
                int mid = (left + right) / 2;
                if(array[mid] > target) {
                    right = mid - 1;
                } else if(array[mid] < target) {
                    left = mid + 1;
                } else {
                    return mid;
                }
            }
            return -1;
        }
    

Log in to reply
 

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