Movatterモバイル変換

[0]ホーム
URL:

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

 Sign up
Appearance settings

Commitbbf3283

Browse files
author
applewjg
committed
4 Sum
Change-Id: I3ecede96a036e6b2682aefdff4b7aacc1bd3bc5a
1 parentbafff47 commitbbf3283

File tree

2 files changed

+95
-0
lines changed

2 files changed

+95
-0
lines changed

‎3SumClosest.java

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
/*
2+
Author: King, wangjingui@outlook.com
3+
Date: Dec 20, 2014
4+
Problem: 3Sum Closest
5+
Difficulty: Medium
6+
Source: https://oj.leetcode.com/problems/3sum-closest/
7+
Notes:
8+
Given an array S of n integers, find three integers in S such that the sum is closest to
9+
a given number, target. Return the sum of the three integers.
10+
You may assume that each input would have exactly one solution.
11+
For example, given array S = {-1 2 1 -4}, and target = 1.
12+
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
13+
14+
Solution: Similar to 3Sum, taking O(n^2) time complexity.
15+
*/
16+
17+
publicclassSolution {
18+
publicintthreeSumClosest(int[]num,inttarget) {
19+
intN =num.length;
20+
if (N <3)return0;
21+
intres =num[0] +num[1] +num[2];
22+
Arrays.sort(num);
23+
for (inti =0;i <N-2; ++i)
24+
{
25+
intl =i +1,r =N -1;
26+
while (l <r)
27+
{
28+
intthreesum =num[i] +num[l] +num[r];
29+
if (threesum ==target)returntarget;
30+
elseif (threesum <target) ++l;
31+
else --r;
32+
if (Math.abs(threesum -target) <Math.abs(res -target))
33+
res =threesum;
34+
}
35+
}
36+
returnres;
37+
}
38+
}

‎4Sum.java

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
/*
2+
Author: King, wangjingui@outlook.com
3+
Date: Dec 20, 2014
4+
Problem: 4Sum
5+
Difficulty: Medium
6+
Source: https://oj.leetcode.com/problems/4sum/
7+
Notes:
8+
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0?
9+
Find all unique triplets in the array which gives the sum of zero.
10+
Note:
11+
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target?
12+
Find all unique quadruplets in the array which gives the sum of target.
13+
Note:
14+
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a <= b <= c <= d)
15+
The solution set must not contain duplicate quadruplets.
16+
For example, given array S = {1 0 -1 0 -2 2}, and target = 0.
17+
A solution set is:
18+
(-1, 0, 0, 1)
19+
(-2, -1, 1, 2)
20+
(-2, 0, 0, 2)
21+
22+
Solution: Similar to 3Sum, 2Sum.
23+
*/
24+
25+
publicclassSolution {
26+
publicList<List<Integer>>fourSum(int[]num,inttarget) {
27+
intN =num.length;
28+
List<List<Integer>>res =newArrayList<List<Integer>>();
29+
if (N <4)returnres;
30+
Arrays.sort(num);
31+
for (inti =0;i <N; ++i)
32+
{
33+
if (i >0 &&num[i] ==num[i-1])continue;// avoid duplicates
34+
for (intj =i+1;j <N; ++j)
35+
{
36+
if (j >i+1 &&num[j] ==num[j-1])continue;// avoid duplicates
37+
inttwosum =target -num[i] -num[j];
38+
intl =j +1,r =N -1;
39+
while (l <r)
40+
{
41+
intsum =num[l] +num[r];
42+
if (sum ==twosum) {
43+
ArrayList<Integer>tmp =newArrayList<Integer>();
44+
tmp.add(num[i]);tmp.add(num[j]);tmp.add(num[l]);tmp.add(num[r]);
45+
res.add(tmp);
46+
while (l <r &&num[l+1] ==num[l])l++;// avoid duplicates
47+
while (l <r &&num[r-1] ==num[r])r--;// avoid duplicates
48+
l++;r--;
49+
}
50+
elseif (sum <twosum)l++;
51+
elser--;
52+
}
53+
}
54+
}
55+
returnres;
56+
}
57+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp