LeetCode之两数之和

╰+哭是因爲堅強的太久メ 2022-05-27 12:05 186阅读 0赞

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9
    
    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]

思路一：最直接的思维，两次遍历查询，时间复杂度O(N\*N)。

代码：

public static int[] twoSum1(int[] nums, int target) {
    		int[] label = new int[2];
    		for(int i=0;i<nums.length-1;i++) {
    			int tmp = target - nums[i];
    			for(int j=i+1;j<nums.length;j++) {
    				if(tmp == nums[j]) {
    					label[0] = i;
    					label[1] = j;
    				}
    			}
    		}
    		return label;
    	}

思路二：先排序，然后两个指针i,j，i从前开始，j从后开始查找，当nums\[i\]+nums\[j\]>target时，j--；当nums\[i\]+nums\[j\]<target时，i++；注意排序后，之前的下标数字已经变化了。时间复杂度O(N\*Log2N)

代码：

public static int[] twoSum2(int[] nums, int target) {
    		int[] label = new int[2];
    		int[] tmpArr = new int[nums.length];
    		for(int i=0;i<nums.length;i++) {
    			tmpArr[i]=nums[i];
    		}
    		Arrays.sort(nums);
    		int i=0;
    		int j=nums.length-1;
    		while (i<j) {
    			if(nums[i]+nums[j]==target) {
    				label[0] = nums[i];
    				label[1] = nums[j];
    				break;
    			}else if(nums[i]+nums[j]>target){
    				j--;
    			}else {
    				i++;
    			}
    		}
    		for(int k=0;k<tmpArr.length;k++) {
    			if(tmpArr[k]==label[0]) {
    				label[0]=k;
    			}
    			if(tmpArr[k]==label[1]) {
    				label[1]=k;
    			}
    		}
    		return label;
    	}

思路三：利用空间换时间方式，用hashmap存储数组结构，key为值，value为下标。时间复杂度O(N)。

代码：

public static int[] twoSum3(int[] nums, int target) {
    		int[] label = new int[2];
    		HashMap<Integer, Integer> hashMap = new HashMap<>();
    		for(int i=0;i<nums.length;i++) {
    			hashMap.put(nums[i], i);
    		}
    		for(int i=0;i<nums.length;i++) {
    			if(hashMap.containsKey(target-nums[i])&&hashMap.get(target-nums[i])!=i) {
    				label[0] = i;
    				label[1] = hashMap.get(target-nums[i]);
    				break;
    			}
    		}
    		return label;
    	}

github地址： [https://github.com/xckNull/Algorithms-introduction][https_github.com_xckNull_Algorithms-introduction]

[https_github.com_xckNull_Algorithms-introduction]: https://github.com/xckNull/Algorithms-introduction