Leetcode - 3Sum Smaller

https://leetcode.com/problems/3sum-smaller/

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

Example:

Input: nums = [-2,0,1,3], and target = 2
Output: 2 
Explanation: Because there are two triplets which sums are less than 2:
             [-2,0,1]
             [-2,0,3]

func threeSumSmaller(nums []int, target int) int {
    sort.Ints(nums)
    i := 0
    j := 0
    count := 0
    for i = 0; i < len(nums)-2; i++ {
        j = i+1
        k := len(nums)-1
        for j < k {
            sum := nums[i] + nums[j] + nums[k]
            if sum < target {
                count += k - j
                j++
            } else {
                k--
            }
        }
    }
    return count
}

1. sort
2. use 3 pointers to calculate the sum

• 相关文章
• 全局相关文章