LeetCode百题【两数之和】

题目描述

题目描述.png

解法一（暴力穷举法）

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result=new int[2];
        for (int i = 0; i <nums.length ; i++) {
            for (int j = i+1; j <nums.length; j++) {
               if(nums[i]+nums[j]==target){
                   result[0]=i;
                   result[1]=j;
                   return result;
               }
            }
        }
      return result;
    }
}

时间复杂度：O(N^2)，其中 NN 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。
空间复杂度：O(1)。

暴力穷举.png

解法二（通过HashMap键值对实现）

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result=new int[2];
     Map<Integer,Integer> map=new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int another=target-nums[i];
            Integer isNum=map.get(another);
            if(isNum!=null){
                result[0]=isNum;
                result[1]=i;
                break;
            }
            else map.put(nums[i],i);
        }
    return result;
}
}