[leetcode] 259.3sum smaller

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].



解题思路
本题是3 sum的变种题,求三个数之和小于一个目标值的组数,和3 sum一样的思路,将3个数之和求出与目标值比较,如果小,结果加一。
代码如下:

class Solution{
public:
    int threeSumSmaller(vector<int>& nums, int target) {
          sort(nums.begin(), nums.end());
          int res = 0;
          int number = nums.size();
          for(int i = 0; i < number - 2; ++i)
          {
                int l = i + 1 , r= number - 1;
                while(l < r)
                {
                    if(nums[i] + nums[l] + nums[r] < target)
                    {
                          res++;
                          l++;
                    } else{
                          r--;
                    }    
                }
          }
          return res;
    }
};

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,768评论 0 33
  • **2014真题Directions:Read the following text. Choose the be...
    又是夜半惊坐起阅读 9,811评论 0 23
  • 今天看到一句话,很有感触,正是我做过的唉。你写了成千条微博朋友圈说说,里面含有各种心情,我会去说我看完了你写的所...
    LOVE20阅读 242评论 0 1
  • 刷朋友圈,看到有人发这么一段话:“对我关闭朋友圈的亲们,我也把你拉黑了!” 因为认识,我找她聊起了这个话题,我说,...
    忆灰泠阅读 219评论 2 2
  • 我记得去年元旦写的年终总结是跟那首宋诗有关:“满川风雨看潮生。”后来真去看了海,金灿灿的阳光打在恬静的海面上,凛冽...
    July鲸鱼阅读 363评论 0 0