259. 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 conditionnums[i] + nums[j] + nums[k] < target.

For example, given nums = [-2, 0, 1, 3], and target = 2.

Return 2. Because there are two triplets which sums are less than 2:

[-2, 0, 1]
[-2, 0, 3]

Follow up:
Could you solve it in O(n2) runtime?

这道题的解法与所有的3 sum,4 sum一样。唯一的区别在于两边往中间找的时候,如果小于dif,那么中间所有的都满足小于的情况,比如[3,1,0,-2], 4。 Sort完是[-2,0,1,3], 一开始选-2时,dif为6,left为1,right为3,小于dif,则以right为一个,left从左一直到right-1的组合都是满足要求的。

public int ThreeSumSmaller(int[] nums, int target) {
        Array.Sort(nums);
        var res =0;
        int size = nums.Count();
        for(int i =0;i< size;i++)
        {
            int num = nums[i];
            int dif = target - num;
            int left =i+1;
            int right = size -1;
            while(left<right)
            {
                if(nums[left]+nums[right] < dif)
                {
                    res+=right-left;
                    left++;
                }
                else right--;
            }
        }
        return res;
    }
时间: 09-25

259. 3Sum Smaller的相关文章

LeetCode 259. 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. For example, given nums = [-2, 0, 1, 3], and target = 2. Retu

Leetcode 259. 3Sum Smaller

1 class Solution(object): 2 def threeSumSmaller(self, nums, target): 3 """ 4 :type nums: List[int] 5 :type target: int 6 :rtype: int 7 """ 8 nums.sort() 9 n = len(nums) 10 ans = 0 11 12 for k in range(n): 13 i, j = k+1, n-1 1

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. For example, given nums = [-2, 0, 1, 3], and target = 2. Retu

3Sum Smaller 解答

Question 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. For example, given nums = [-2, 0, 1, 3], and target 

3Sum Smaller -- LeetCode

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. For example, given nums = [-2, 0, 1, 3], and target = 2. Retu

leetcode 锁掉的题目清单

也刷leetcode, 先把锁掉的题目留备份好了: 156 Binary Tree Upside Down  [1] Problem: Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tre

过中等难度题目.0310

  .   8  String to Integer (atoi)    13.9% Medium   . 151 Reverse Words in a String      15.7% Medium     . 288 Unique Word Abbreviation      15.8% Medium     . 29 Divide Two Integers      16.0% Medium     . 166 Fraction to Recurring Decimal      17.

Sum 类型题目总结

Sum类的题目一般这样: input: nums[], target output: satisfied arrays/ lists/ number 拿到题目,首先分析: 1. 是几个数的sum 2. sum是要求等于target还是小于还是大于还是closest 3. 返回的是原数组下标还是其他 对于这类题目,我们经常用双指针的方法.即排序后,左指针指向起点,右指针指向终点. 如果sum等于target,加入结果/总数目+1 如果sum大于target,右指针左移 如果sum小于target,

LintCode Triangle Count

原题链接在这里:http://www.lintcode.com/en/problem/triangle-count/# 题目: Given an array of integers, how many three numbers can be found in the array, so that we can build an triangle whose three edges length is the three numbers that we find? Example Given a