Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
public class Solution {
public int[] twoSum(int[] numbers, int target) {
// Start typing your Java solution below
// DO NOT write main() function
if(numbers==null) return null;
int[] now = new int[numbers.length];
System.arraycopy(numbers,0,now,0,numbers.length);
Arrays.sort(numbers);
int i = 0,j=numbers.length-1;
while(i<j){
if(numbers[i]+numbers[j]>target){
j--;
}else if(numbers[i]+numbers[j]<target){
i++;
}else{
int x =0;
for(x=0;x<now.length;x++){
if(now[x]==numbers[i])
break;
}
//注意题目希望返回下标，所以要留意重新排序后造成的下标变化问题
int y=0;
for(y=0;y<now.length;y++){
if(x!=y && now[y]==numbers[j])
break;
}
/*
if(now[x]<now[y]){
int temp = x;
x=y;
y=temp;
}*/
int [] res = new int[2];
res[0]=x+1;
res[1]=y+1;
Arrays.sort(res); //返回的下标是要有序的！
return res;
}
}
return null;
}
}Line 16: ']' expected
Line 24: missing return statement
Last executed input[5,75,25], 100
Showing the first failed test case.
| input | output | expected | |
|---|---|---|---|
| [5,75,25], 100 | 1, 2 | 2, 3 |
|
Showing the first failed test case.
| input | output | expected | |
|---|---|---|---|
| [150,24,79,50,88,345,3], 200 | 3, 6 | 1, 4 |
|
Line 7: incompatible types
Line 8: cannot find symbol: method copy(int[],int[])
Line 8: cannot find symbol: method copyOf(int[],int[])
Line 29: cannot find symbol: variable x
Showing the first failed test case.
| input | output | expected | |
|---|---|---|---|
| [5,75,25], 100 | 3, 2 | 2, 3 |
|
Showing the first failed test case.
| input | output | expected | |
|---|---|---|---|
| [5,75,25], 100 | 3, 2 | 2, 3 |
|
Showing the first failed test case.
| input | output | expected | |
|---|---|---|---|
| [5,75,25], 100 | 3, 2 | 2, 3 |
|
Showing the first failed test case.
| input | output | expected | |
|---|---|---|---|
| [2,1,9,4,4,56,90,3], 8 | 4, 4 | 4, 5 |
|
Showing the first failed test case.
| input | output | expected | |
|---|---|---|---|
| [230,863,916,585,981,404,316,785,88,12,70,435,384,778,887,755,740,337,86,92,325,422,815,650,920,125,277,336,221,847,168,23,677,61,400,136,874,363,394,199,863,997,794,587,124,321,212,957,764,173,314,422,927,783,930,282,306,506,44,926,691,568,68,730,933,737,531,180,414,751,28,546,60,371,493,370,527,387,43,541,13,457,328,227,652,365,430,803,59,858,538,427,583,368,375,173,809,896,370,789], 542 | 46, 29 | 29, 46 |
|
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)
public class Solution {
public static ArrayList<ArrayList<Integer>> threeSum(int[] num) {
// Start typing your Java solution below
// DO NOT write main() function
if (num == null)
return null;
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
Arrays.sort(num);
for (int i = 0; i < num.length-2; i++) {
if (i > 0 && num[i] == num[i - 1]) continue;
int j = i + 1, k = num.length - 1;
while (j < k) {
if (num[j] + num[k] > -num[i]) {
k--;
} else if (num[j] + num[k] < -num[i]) {
j++; // 写错成i了....
} else {
ArrayList<Integer> a = new ArrayList<Integer>();
a.add(num[i]); //放的不是ijk 而是他们的值！
a.add(num[j]);
a.add(num[k]);
list.add(a);
j++; //这些步骤是为了排除掉 j k里面存在重复的地方！
k--;
while(j<k && num[j]==num[j-1]) j++;
while(j<k && num[k]==num[k+1]) k--;
}
}
}
return list;
}
}
Line 27: illegal start of type
Showing the first failed test case.
| input | output | expected | |
|---|---|---|---|
| [] | null | [] |
|
Showing the first failed test case.
| input | output | expected | |
|---|---|---|---|
| [0,0,0] | [] | [[0,0,0]] |
|
Showing the first failed test case.
| input | output | expected | |
|---|---|---|---|
| [0,0,0] | [[0,1,2]] | [[0,0,0]] |
|
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
public class Solution {
public int threeSumClosest(int[] num, int target) {
// Start typing your Java solution below
// DO NOT write main() function
if(num==null) return -1;
int goal = 0; //不设为最大值！ 因为加加减减会造成溢出！
boolean ifinit = false; //加入变量，来让goal有个初值！
Arrays.sort(num);
for(int i=0;i<num.length-2;i++){
if(i>0 && num[i]==num[i-1]) continue;
int j= i+1,k=num.length-1;
while(j<k){
int now = num[i]+num[j]+num[k];
if(!ifinit||Math.abs(now-target)<Math.abs(goal-target) ){
goal = now;
ifinit = true;
}
if(now>target){
k--;
while(j<k && num[k]==num[k+1]) k--; //前提条件！！！
}else{
j++;
while(j<k && num[j]==num[j-1]) j++;
}
}
}
return goal;
}
}Line 16: ')' expected
Last executed input[0,0,0], 1
Showing the first failed test case.
| input | output | expected | |
|---|---|---|---|
| [1,1,-1,-1,3], -1 | 2147483647 | -1 |
|
Line 17: cannot find symbol: variable init
Line 17: variable goal might not have been initialized
4sum 大数据超时 时间复杂度 n*3
public static ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
if(num==null) return null;
Arrays.sort(num);
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>> ();
for(int i=0;i<num.length-3;i++){
if(i>0 && num[i]==num[i-1]) continue;
for(int j=i+1;j<num.length-2;j++){
if(j>i+1 && num[j]==num[j-1]) continue; //这里请注意j是从i+1开始的！！！
int k = j+1,m = num.length-1;
while(k<m){
if(num[i]+num[j]+num[k]+num[m]==target){
ArrayList<Integer> a = new ArrayList<Integer>();
a.add(num[i]);
a.add(num[j]);
a.add(num[k]);
a.add(num[m]);
list.add(a);
k++;
m--;
while(k<m && num[k]==num[k-1]) k++;
while(k<m && num[m]==num[m+1]) m--;
}else if(num[i]+num[j]+num[k]+num[m]>target){
m--;
}else{
k++;
}
}
}
}
return list;
}因篇幅问题不能全部显示，请点此查看更多更全内容