乐趣区

leetCode第一题

leetCode 第一题

普通解决思路

将数组变量两次,相加判断是否等于传过来的值,如果等于,返回下标
自己写的代码,如果有错误请指出,谢谢

package com.leetcode.firstquestion.one;

import java.util.Arrays;

/**
 * @program: test
 * @description: 两数之和 给定一个整数数组 nums 和一个目标值 target,*                       请你在该数组中找出和为目标值的那
 *                       两个 整数,并返回他们的数组下标。* @author: Mr.Yang
 * @create: 2019-05-08 09:20
 **/
public class Solution {public int[] twoSum(int[] nums, int target) {int[] ints = new int[2];
        int indexOne=0;
        int indexTwo=0;
        boolean flag=false;
        for(int x=0;x<nums.length;x++){for(int y=x+1;y<nums.length;y++){if((nums[x]+nums[y])==target){
                    indexOne=x;
                    indexTwo=y;
                    flag=true;
                    break;
                }
            }
            if(flag){break;}
        }
        ints[0]=indexOne;
        ints[1]=indexTwo;
        return ints;
    }

    public static void main(String[] args) {int[] ints = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        Solution solution = new Solution();
        int[] ints1 = solution.twoSum(ints, 9);
        System.out.println(Arrays.toString(ints1));
    }
}

网上流传思路,使用 HashMap 来处理

将数组的遍历值当作 key(为了存取好处理,所以将数组的遍历值当作 key),索引当作 value 来存储。

package com.leetcode.firstquestion.two;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @program: test
 * @description: 两数之和 给定一个整数数组 nums 和一个目标值 target,*                       请你在该数组中找出和为目标值的那
 *                       两个 整数,并返回他们的数组下标。* @author: Mr.Yang
 * @create: 2019-05-08 09:20
 **/
public class Solution {public int[] twoSum(int[] nums, int target) {HashMap<Object, Integer> argsMap = new HashMap<>();
        for(int i=0;i<nums.length;i++){int value = nums[i];
            if(argsMap.containsKey(target - value)){return new int[]{i, argsMap.get(target - value)};
            }
            argsMap.put(value,i);
        }
        return null;
    }

    public static void main(String[] args) {int[] ints = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        Solution solution = new Solution();
        int[] ints1 = solution.twoSum(ints, 9);
        System.out.println(Arrays.toString(ints1));
    }
}
  • 相比较自己写的那个确实要好得多,自己那个需要遍历两次,简单时间复杂度 O(n2)
  • 网上的方法,简单时间复杂度 O(n)
退出移动版