数码吧

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