找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 5944|回复: 1
收起左侧

[米群网刷题小分队] LeetCode - 3Sum Smaller 会员题

[复制链接]

14

主题

0

精华

52

积分

资深会员

Rank: 2

积分
52
发表于 8-22-2015 06:06 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
題目:

Given an array of 【i】n integers 【i】nums and a 【i】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 【i】nums = [-2, 0, 1, 3], and 【i】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 【i】O(【i】n2) runtime?



思路:
这题用O(n^3)暴力解法也会过, 下面给的是O(n^2)的解法
这题有一个题目没有说清楚的地方是, 重复的解答都要计算在内, 比如说:
[0, 1, 1, 1], target = 3, 这样算3个解答 [index[0] , index[1], index[2]]   [index[0], index[1], index[3]] [index[0], index[2], index[3]]


另外下面的代码中, 如果sum >= target 则 j--, 这好理解.
比较关键的地方是, 如果sum < target 那麽 j - i 都是解:


  1. public int threeSumSmaller(int[] nums, int target) {
  2.     int n = nums.length;
  3.     Arrays.sort(nums);
  4.         
  5.     int count = 0;
  6.     for (int k = 0; k < n - 2; k++) {
  7.         int i = k + 1;
  8.         int j = n - 1;
  9.         while (i < j) {
  10.             int sum = nums[k] + nums【i】 + nums[j];
  11.             if (sum >= target) {
  12.                 j--;
  13.             } else {
  14.                 count += j - i;
  15.                 i++;
  16.             }
  17.         }
  18.     }
  19.         
  20.     return count;
  21.     }
复制代码





14

主题

0

精华

52

积分

资深会员

Rank: 2

积分
52
 楼主| 发表于 8-22-2015 07:32 AM | 显示全部楼层
题目格式没弄好 重贴如下

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.

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(n^2) runtime?
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表