专栏首页Jacob【LeetCode】两数之和

【LeetCode】两数之和

package leetcode.editor.cn;

//给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 
//
// 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。 
//
// 
//
// 示例: 
//
// 给定 nums = [2, 7, 11, 15], target = 9
//
//因为 nums[0] + nums[1] = 2 + 7 = 9
//所以返回 [0, 1]
// 
// Related Topics 数组 哈希表

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

public class 两数之和{
	public static void main(String[] args) {
		Solution solution = new 两数之和().new Solution();
		int[] arr = {2,7,11,15};
		int target = 9;
		System.out.println(Arrays.toString(solution.twoSum(arr,target)));
		System.out.println(Arrays.toString(solution.twoSum2(arr,target)));
		System.out.println(Arrays.toString(solution.twoSum3(arr,target)));

	}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	/**
	 * 方法一:一遍哈希表
	 * 在进行迭代并将元素插入到表中的同时,我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在,那我们已经找到了对应解,并立即将其返回。
	 * 简单点说:和减去当前遍历元素得到另一元素,判断另一元素是否在哈希表中,存在即返回;不存放将当前遍历元素,存放哈希表中。
	 * @param nums
	 * @param target
	 * @return
	 */
    public int[] twoSum(int[] nums, int target) {
		Map<Integer,Integer> map = new HashMap<Integer, Integer>();
		for (int i = 0; i < nums.length; i++) {
			int temp = target - nums[i];
			if(map.containsKey(temp)){
				return new int[]{map.get(temp),i};
			}
			map.put(nums[i],i);
		}
		return null;
    }

	/**
	 * 方法二:两遍哈希表
	 * 将数组元素存放在哈希表中,再循环辨析数组,判断哈希表中是否存在元素相加等于和。
	 * @param nums
	 * @param target
	 * @return
	 */
	public int[] twoSum2(int[] nums, int target) {
		Map<Integer,Integer> map = new HashMap<Integer, Integer>();
		for (int i = 0; i < nums.length; i++) {
			map.put(nums[i],i);
		}
		for (int i = 0; i < nums.length; i++) {
			int temp = target - nums[i];
			if(map.containsKey(temp) && map.containsKey(nums[i])){
				return new int[]{map.get(nums[i]),map.get(temp)};
			}
		}
		return nums;
	}

	/**
	 * 方法三:暴力解题法
	 * 遍历两次数组
	 * @param nums
	 * @param target
	 * @return
	 */
	public int[] twoSum3(int[] nums, int target) {
		for (int i = 0; i < nums.length-1; i++) {
			for (int j = i+1; j < nums.length; j++) {
				if (target == (nums[i]+nums[j])){
					return new int[]{i,j};
				}
			}
		}
		return nums;
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【LeetCode】回文数

    Jacob丶
  • cron 表达式详解

      Cron表达式是一个字符串,字符串以5或6个空格隔开,分为6或7个域,每一个域代表一个含义,Cron有如下两种语法格式:

    Jacob丶
  • Integer 值判断相等

    通过案例发现,值为127不管是 Integer 还是 String 类型,== 和 equals 都能比较成功。128与类型无关,与比较的方法有关。

    Jacob丶
  • 【LeetCode】两数之和

    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。

    弗兰克的猫
  • 查找数组中两数之和等于指定的数

    题目:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

    Melody132
  • 哈希表-LeetCode 217、219、220、232(hashset、hashmap)

    给定一个整数数组,判断是否存在重复元素。 如果任何值在数组中出现至少两次,函数返回 true。如果数组中每个元素都不相同,则返回 false。

    算法工程师之路
  • 【LeetCode】找出数组中重复的数字day01

    居士
  • 剑指Offer题解

    在一个长度为n+1的数组里的所有数字都在1~n的范围内,所以数组中至少存在一个数字是重复的。 请找出数组中任意一个重复的数字,但不能修改输入的数组。 例如输...

    星如月勿忘初心
  • 【LeetCode】136. Single Number

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • Largest Number Greater Than Twice of Others

    思路1: 非排序,如果存在一个数,比其他任何数的两倍还大必然是最大数。时间复杂度为O(n2)O(n^2)

    用户1147447

扫码关注云+社区

领取腾讯云代金券