My solutions in Java and Python


  • 2

    Java:

    public class Solution {
        public int threeSumSmaller(int[] nums, int target) {
            Arrays.sort(nums);
            int total = 0;
            for (int i = 0; i < nums.length; i++) {
                total += this.twoSumSmaller(nums, i + 1, nums.length - 1, target - nums[i]);
            }
            return total;
        }
        
        private int twoSumSmaller(int[] nums, int start, int end, int target) {
            int total = 0;
            while (start < end) {
                if (nums[start] + nums[end] >= target) {
                    end--;
                } else {
                    total += (end - start++);
                }
            }
            return total;
        }
    }
    

    Python:

    class Solution:
        # @param {integer[]} nums
        # @param {integer} target
        # @return {integer}
        def threeSumSmaller(self, nums, target):
            nums.sort()
            total, length = 0, len(nums)
            for i in range(length):
                j, k = i + 1, length - 1
                while j < k:
                    if nums[i] + nums[j] + nums[k] < target:
                        total, j = total + k - j, j + 1
                    else:
                        k -= 1
            return total

Log in to reply
 

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