import java.util.*;
/**
給定一個整數(shù)數(shù)組 nums 和一個目標(biāo)值 target秸应,請你在該數(shù)組中找出和為目標(biāo)值的那 兩個 整數(shù),并返回他們的數(shù)組下標(biāo)。
你可以假設(shè)每種輸入只會對應(yīng)一個答案软啼。但是桑谍,你不能重復(fù)利用這個數(shù)組中同樣的元素。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
-
所以返回 [0, 1]
/
public class TwoSum {
/*- 解法1
- @param nums
- @param target
- @return
*/
public int[] twoSum(int[] nums, int target) {
int[] tmp=nums.clone();
Arrays.sort(nums);
int i=0;
int j=nums.length-1;
List<Integer> result = new ArrayList<>();
while(i<j){
int sum = nums[i]+nums[j];
if(sum==target){
result.add(nums[i]);
result.add(nums[j]);
break;
}else if(sum<target){i++;}
else if(sum>target){j--;}
}
if(result.size()==0) return null;
int count=0;
int[] result1 = new int[2];
for(int n=0;n<tmp.length;n++){
if(tmp[n]==result.get(0)||tmp[n]==result.get(1)){
result1[count]=n;
count++;
}
if(count==2) break;
}
return result1;
}
/**
- 解法2
- @param nums
- @param target
- @return
*/
public int[] twoSum1(int[] nums, int target) {
Map<Integer,Integer> hash = new HashMap<>();
for(int i=0;i<nums.length;i++){
int num2 = target-nums[i];
if(hash.containsKey(num2)){
return new int[]{hash.get(num2),i};
}else{
if(!hash.containsKey(nums[i])){
hash.put(nums[i],i);
}
}
}
return null;
}
/**
- 解法3
- @param args
*/
public int[] twoSum3(int[] nums, int target) {
for(int i=0;i<nums.length;i++){ for(int j=i+1;j<nums.length;j++){ if(nums[i]+nums[j]==target){ return new int[]{i,j}; } } } return null;
}
public static void main(String[] args){
int[] num = {3,3};
int target = 6;
TwoSum solution = new TwoSum();
int[] s = solution.twoSum1(num,target);
System.out.print("["+s[0]+","+s[1]+"]");
}
}