头像

带翅膀的猫

时光荏苒,我们一直都在

《LeetCode刷题(Easy Rank):1.Two Sum》

 1月前  •   LeetCode  •     •   33  •   0

Question:

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, and you may not use the same element twice.

Example:

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

题目要我们找出两个数之和等于指定的target,并且返回两个数的下标。同时每一个元素只能使用一次。

一、普通解法,俗套

JAVA//第一印象想到的普通解法,暴力搜索,不用说这解法不引人注目,不多介绍 
public int[] twoSum(int[] nums, int target) { 
	int[] result = new int[2]; 
	if (nums == null || nums.length < 2) { 
		return result ; 
	} 
	int sum=0; 
	for(int i=0;i<nums.length-1;i++){ 
		int left=i; 
		for(int j=i+1;j<nums.length;j++){ 
			int right=j; 
			if(nums[left]+nums[right]==target){ 
				result[0]=left; 
				result[1]=right; 
				break; 
			} 
		} 
	} 
	return result; 
}

2、使用HashMap空间换时间

JAVApublic int[] twoSum(int[] nums, int target){ 
	int[] res = new int[2]; 
	if (nums == null || nums.length < 2) { 
		return res; } 
	Map<Integer, Integer> map = new HashMap<Integer, Integer>(); 
	for (int i = 0; i < nums.length; i++) { 
		int temp = target - nums[i];//两个数之和为target,target减去当前扫描的数我们只需要找到另外一个数就可以了 
		if (map.containsKey(temp)) {//map中包含另外一个数,找到了 
			res[0] = map.get(temp); 
			res[1] = i; 
			return res; 
		} else { 
			map.put(nums[i], i);//map中不存在另一个数,将当前扫描到的值放入map中,同时也要保持i 
		} 
	} 
	return res; 
} 
/*
拿题目中的例子来说:首先扫描到2,我们此时要找7,map中没有7,所有将2及其下标1放入map中;
然后我们扫描到7,我们此时要找2,map中包含了2,直接获取2的下标,结束。
我个人将它命名为:交换查找。
*/

3、运用二分法,更加快哦

JAVApublic int[] twoSum3(int[] nums, int target){
    int[] res = new int[2];
    if (nums == null || nums.length < 2) {
        return res;
    }
    int[] oldNums = Arrays.copyOf(nums, nums.length);//保留原数组
    Arrays.sort(nums);//运用二分法数组必须是有序的
    
    for(int i=0;i<nums.length;i++){
    	int currTarget = target - nums[i];//还是老思路,固定一个,找另一个
    	int index = binarySearch(nums, 0, nums.length-1, currTarget);
    	if(index==-1){
    		continue;//返回-1,说明不存在另一个数和当前数加起来满足target
    	}
    	if(index!=-1&&index!=i){//返回1,并且不是当前那个元素,说明找到了另一个满足条件的数
    		int answerIndex = 0;
    		//将两个数和原数组下标对应上
            for (int j = 0; j < nums.length; j++) {
                if (oldNums[j] == nums[i]) {
                    res[answerIndex++] = j;
                }
                else if (oldNums[j] == currTarget) {
                    res[answerIndex++] = j;
                }
            }
            return res;
    	}
    }
    return res;
}

//二分查找,经典算法
public int binarySearch(int[] nums,int left,int right,int target){
    int mid = (left+right)/2;
    while(left<=right){
	if(nums[mid]==target){
		return mid;
	}
	if(nums[mid]<target){
		left = mid+1;
	}else{
		right = mid-1;
	}
	mid = (left+right)/2;
    }
    return -1;
}
上一篇:
下一篇:

 评论


 已有0条评论

    还没有任何评论,你来说两句吧!