Leetcode - Two Sum Less Than K
Leetcode - Add and Search Word - Data structure design

Leetcode - 3Sum Smaller

violet posted @ Mar 28, 2020 01:56:01 AM in 算法 with tags Algorithm 3sum array , 174 阅读

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

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter