TwoSum问题

深碍√TFBOYSˉ_ 2022-07-26 02:01 119阅读 0赞

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

Given nums = [2, 7, 11, 15], target = 9,
    
    Because nums[0] + nums[1] = 2 + 7 = 9,
    return [0, 1].

我的算法

public int[] solution(int[] nums,int target){
    		Map<Integer,Integer> map=new HashMap<Integer,Integer>();
    		int[] res=new int[2];
    		for(int i=0;i<nums.length;i++){
    			if(map.containsKey(target-nums[i])){
    				res[0]=i;
    				res[1]=map.get(target-nums[i]);
    			}
    			map.put(nums[i], i);
    		}
    		return res;
    	}

网上还有一种不使用HashMap的方法，但是当数组中有重复的数出现时可能会出现数组越界问题

public int[] solution2(int[] nums,int target){
    		int[] nums_sorted=new int[nums.length];
    		System.arraycopy(nums,0, nums_sorted, 0, nums.length);
    		
    		Arrays.sort(nums_sorted);
    		
    		int start=0;
    		int end=nums_sorted.length;
    		while(start<end){
    			while(nums_sorted[start]+nums_sorted[--end]>target);
    			if(nums_sorted[start]+nums_sorted[end]==target)
    				break;
    			while(nums_sorted[++start]+nums_sorted[end]<target);
    			if(nums_sorted[end]+nums_sorted[start]==target)
    				break;
    		}
    		
    		int[] res=new int[2];
    		int index=0;
    		int a=nums_sorted[start];
    		int b=nums_sorted[end];
    		for(int i=0;i<nums.length;i++){
    			if(nums[i]==a||nums[i]==b)
    				res[index++]=i;
    		}
    		return res;
    	}

加油！ ![得意][proud.gif]

[proud.gif]: /images/20220724/a7f356065a054ed9bde630301749a415.png

发表评论取消回复

表情：

评论列表（有 0 条评论，119人围观）

还没有评论，来说两句吧...

相关阅读

相关 TwoSum 相关问题思路总结

击蓝色“五分钟学算法”关注我哟加个“星标”，天天中午 12:15，一起学算法 ![640?wx\_fmt=jpeg][640_wx_fmt_jpeg] 作者 | ...

约定不等于承诺〃/ 2024年04月19日 08:33/ 0 赞/ 68 阅读

相关 leetcode 第一题 twoSum

题目：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，

迈不过友情╰/ 2022年10月29日 09:21/ 0 赞/ 140 阅读

相关 LeetCode之TwoSum

描述: Given an array of integers, find two numbers such that they add up to a specific t

灰太狼/ 2022年08月05日 01:28/ 0 赞/ 172 阅读

相关 TwoSum问题

Given an array of integers, return indices of the two numbers such that they add up to a

深碍√TFBOYSˉ_/ 2022年07月26日 02:01/ 0 赞/ 120 阅读

相关 leetcode-01 TwoSum

leetcode-01 TwoSum Given nums = [2, 7, 11, 15], target = 9, Because nums

Myth丶恋晨/ 2022年06月17日 10:26/ 0 赞/ 170 阅读

相关 1_twoSum

> Given an array of integers, return indices of the two numbers such that they add up to

墨蓝/ 2022年06月12日 14:43/ 0 赞/ 152 阅读

相关 LeetCode TwoSum题解

题目 Given an array of integers, return indices of the two numbers such that they add u

淡淡的烟草味﹌/ 2022年06月12日 07:48/ 0 赞/ 194 阅读

相关 ARTS LeetCode1 TwoSum

two Sum Given an array of integers, return indices of the two numbers such that they ad

傷城~/ 2022年03月01日 21:16/ 0 赞/ 195 阅读

相关 Java实现有序数组TwoSum

题目：升序数组找出两个数的和为target，返回它们的下标 //定义左右两个指针，向中间遍历，如果两数之和等于target返回下标 //小于target，左指

ゞ浴缸里的玫瑰/ 2022年02月04日 19:21/ 0 赞/ 186 阅读

相关 TwoSum问题

问题描述：给定一个整数数组，返回两个数字的索引，使它们相加的值等于一个特定的目标值。假设对于每个输入只有一种解决方案，并且您不可以两次同时使用相同的元素。问题的示例：

╰半夏微凉°/ 2022年01月27日 09:45/ 0 赞/ 155 阅读