1. 两数之和 暴力解法 ：通过两个for循环逐步遍历，判断是否有符合条件的答案 1.初始有对数据进行判断，比如数字比目标值大就不用判断，直接跳过，其实是不行的，因为里面有负数
暴力解法：通过两个for循环逐步遍历，判断是否有符合条件的答案- 1.初始有对数据进行判断，比如数字比目标值大就不用判断，直接跳过，其实是不行的，因为里面有负数，最后相减也可以得出正确答案，这是最初版本。
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] dp = new int[2];
for(int i = 0 ;i <nums.length;i++){
if(nums[i]>Math.abs(target)){
continue;
}else{
for(int j = i+1;j<nums.length;j++){
if(target == nums[i]+nums[j]){
dp[0] = i;
dp[1] = j;
}
}
}
}
return dp;
}
}
- 2.之后发现有负数这种情况后，直接取消了判断，但这样会增加时间复杂度，没有做好优化。
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] dp = new int[2];
for(int i = 0 ;i <nums.length;i++){
for(int j = i+1;j<nums.length;j++){
if(target == nums[i]+nums[j]){
dp[0] = i;
dp[1] = j;
}
}
}
return dp;
}
}
哈希表法:先将数据存入哈希表中，再使用目标值依次减去数组中的数据，再从哈希表中找是否有符合条件的值，如果有，将下标传给result数组，返回结果。
class Solution {
// HashMap
// N is the size of nums
// Time Complexity: O(N)
// Space COmplexity: O(N)
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
//定义hashMap
HashMap<Integer,Integer> map = new HashMap<>();
for(int i=0;i < nums.length;i++){
//将所有数据存入hash表中
map.put(nums[i],i);
}
//使用目标值减去数组中的值，查看表中是否有符合条件的值就返回
for(int j=0;j < nums.length; j++){
int diff = target - nums[j];
if(map.containsKey(diff)&&map.get(diff)!=j){
result[0] = j;
result[1] = map.get(diff);
return result;
}
}
return result;
}
}
