1. 两数之和

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;    }}