2019年6月23日，立一个flag每天做一道算法题，先坚持100天！中间不定期更新做题的一些感受和做题的方式方法
今天先来第一道题，来自于LeetCode上面的一道题目，同时也是很多公司笔试题中的一道。
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
示例：
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
解题思路：
思路一： 首先已知是一个整型数组，需要两两求和，所以可以通过两个for循环来处理，在这里需要注意第二个for循序只需要从第一个for循环的下标+1处开始循环即可！
该方法的时间去复杂度为O（n^2），空间复杂度为O（1）
public int[] twoSum(int[] nums, int target) {
int[] is = new int[2];
for(int i = 0 ;i <= nums.length ; i++){
for(int j = i+1 ; j <= nums.length -1 ; j++){
int r = nums[i] + nums[j] ;
if(r == target){
is[0] = i ;
is[1] = j ;
}
}
}
return is;
}
思路二：可以通过哨兵，在for循环外面进行计算，用target-num[i] 如果内循环里面有一个等于这个值，则取出下标
public int[] twoSum(int[] nums, int target) {
int[] rs = new int[2];
int flag = 0;
for(int i =0;i <nums.length;i++){
flag = target - nums[i];
for(int j = i+1;j<nums.length;j++){
if(nums[j] == flag){
rs[0] = i;
rs[1] = j;
}
}
}
return rs;
}
思路三：通过hash表存储数组数据，通过空间换取时间方式
时间复杂度为O(n) , 前面循环map存入数据占用的复杂度为n，后面的查询复杂度为1
空间复杂度为O(n)
public int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer> hashMap = new HashMap<>();
int[] res = new int[2];
for(int i=0;i<nums.length;i++){
hashMap.put(nums[i],i);
}
for(int j = 0;j < nums.length ;j++){
int flag = target - nums[j];
if(hashMap.containsKey(flag) && hashMap.get(flag) != j){
res[0] = j;
res[1] = hashMap.get(flag);
return res;
}
}
return res;
}
思路四：通过一个循环法即可得到结果值
时间复杂度为O(n) , 空间复杂度为O(n)
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> hashMap = new HashMap<>();
int[] res = new int[2];
for (int i = 0; i < nums.length; i++) {
int flag = target - nums[i];
if (hashMap.containsKey(flag)) {
res[0] = hashMap.get(flag);
res[1] = i;
return res;
}
hashMap.put(nums[i], i);
}
return res;
}
第四种方式说明一下：
比如数组为：{1,3,6,7,9} ,target = 13
则：第一次循环flag = 13-1 = 12 map中不包含则put进去 map.put(1,0)
第二次循环flag=13-3 = 10 map中不包含则put进去 map.put(3,1)
第三次循环flag=13-6=7 map中不包含7 则put进去 map.put(6,2)
第四次循环flag=13-7=6 此时map中已经包含了7，下标为2 则返回下标2和下标3（7的下标）
网友评论