1

https://leetcode.com/problems/two-sum/description/
输入: nums 数组 ,和 target 整型
处理: 找到 nums 中两个数字相加等于 target
输出: 输入这两个数字的下标

  • 思路1
    循环两次,判断相加是否等于 target

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class  {
    public int[] twoSum(int[] nums, int target) {
    for(int i=0;i<nums.length-1;i++){
    for(int j=i+1;j<nums.length;j++){
    if(nums[i]+nums[j] == target) {
    return new int[]{i,j};
    }
    }
    }
    return new int[]{-1,-1};
    }
    }
  • 思路2
    看了讨论才想到的,惭愧,只需要 O(n),利用 HashMap

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class  {
    public int[] twoSum(int[] nums, int target) {
    HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
    for(int i=0;i<nums.length;i++){
    if(map.containsKey(target-nums[i])){
    return new int[]{map.get(target-nums[i]),i};
    }
    map.put(nums[i],i);
    }
    return new int[]{-1,-1};
    }
    }

类似数字对应的题目都可以考虑用下哈希表,可能会有很好的做法