Java O(n^2) Solution w/ Inline Explanation


  • 1
    R
    public class Solution {
        public int threeSumSmaller(int[] nums, int target) {
            // Spend O(nlogn) to sort the array - we don't need
            // to report all cases, so indices don't matter
            Arrays.sort(nums);
            int count = 0, i, k, nJ, nK;
            // Loop through the middle index
            for (int j = 1; j < nums.length - 1; j++) {
                nJ = nums[j];
                // i scans backwards from j - 1
                i = j - 1;
                // k scans forward from j + 1
                for (k = j + 1; k < nums.length; k++) {
                    nK = nums[k];
                    // Find the largest nI which fits nI + nJ + nK < target
                    while (i >= 0 && nums[i] + nJ + nK >= target) i--;
                    // All numbers in front of nI could be added towards total
                    count += i + 1;
                    // Stop looking for larger k's if i already reaches minimum
                    if (i < 0) break;
                }
            }
            return count;
        }
    }

Log in to reply
 

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