Java O(n^2) Solution


  • 0
    M

    Like the 3Sum problem. Ideas are pretty much the same, I just encapsulate the sub-work into method calls to make the code easier to read.

        public class Solution {
        public int threeSumSmaller(int[] nums, int target) {
            if(nums == null || nums.length < 3)
                return 0;
            int res = 0;
            Arrays.sort(nums);
            for(int left = 0; left < nums.length - 2; left++){
                res += numOfPairs(nums, left + 1, nums.length - 1, target - nums[left]);
            }
            return res;
        }
            // Calculate the number of different pairs that sums to a number less than the target
        private int numOfPairs(int[] nums, int start, int end, int target){
            int res = 0;
            while(start < end){
                int sum = nums[start] + nums[end];
                if(sum < target){
                    res += end - start;
                    start++;
                }
                else{
                    end--;
                }
            }
            return res;
        }
    }
    

Log in to reply
 

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