Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Expand file tree

/

3Sum Smaller.java

Copy path
More file actions
More file actions

Latest commit

 

History

History
History
executable file
·
91 lines (80 loc) · 2.75 KB
/

3Sum Smaller.java

Copy path

File metadata and controls

executable file
·
91 lines (80 loc) · 2.75 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
M
1517465602
tags: Two Pointers, Array
一般的O(n3)肯定不行。在此基础上优化。
发现j,k满足条件时候，(k - j)就是所有 sum <target的情况了。
而一旦>target, 又因为j不能后退，只能k--，那么问题就被锁定了. 这样可以做到O(n2)
```
/*
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(n2) runtime?
Tags: Array Two Pointers
Similar Problems:(M) 3Sum, (M) 3Sum Closest
*/
/*
Thoughts:
For loop over initial selection. Have 2sum solution within (2 pointer).
When < target, count+= end-start, start++.
When >= target, end--.
*/
class Solution {
public int threeSumSmaller(int[] nums, int target) {
if (nums == null || nums.length <= 2) {
return 0;
}
Arrays.sort(nums);
int count = 0;
for (int i = 0; i < nums.length - 2; i++) { // first num, num[i] is the fixed item
int start = i + 1, end = nums.length - 1; // move start, end
while (start < end) {
if (nums[i] + nums[start] + nums[end] < target) {
count += end - start;
start++;
} else {
end--;
}
}
}
return count;
}
}
/*
Thoughts:
Similar to 3 sum, but ofcourse, this one check on '<' so we can not use HashMap anymore.
Basic concept is to fix first number, then check for the rest two numbers, see if they addup < target.
When checking j and k, realize something nice:
if nums[j] + nums[k] < target - nums[i], that means for all index <= k will work, so directly add (k - j) to result (that's: index = j+1, j+2, ....,k)
also, move j forward for next round.
OR, if three-add-up >= target, since j can only increase, we do k-- to make the three-add-up smaller
Note:
Don't forget to sort, otherwise the sequence/order is unpredictable
*/
public class Solution {
public int threeSumSmaller(int[] nums, int target) {
if (nums == null || nums.length <= 2) {
return 0;
}
Arrays.sort(nums);
int rst = 0;
for (int i = 0; i < nums.length - 2; i++) {
int j = i + 1;
int k = nums.length - 1;
while (j < k) {
if (nums[i] + nums[j] + nums[k] >= target) {
k--;
} else {
rst += (k - j);
j++;
}
}
}//END for
return rst;
}
}
```
Morty Proxy This is a proxified and sanitized view of the page, visit original site.