LeetCode——Two Sum

题目:

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

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

Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2

解题过程:

1、分析

   题目的意思是在一个数组中找到两个数,这样的两个数的和等于指定的数,最终返回这样的两个数的下标。

   注意点:

  1. 返回的下标中index1<index2;
  2. 下标不是从0开始的;
  3. 并没有说数组是有序的。

2、解题思路

2.1若是有序数组

   对于有序数组,可以通过从两端向中间的方法来进行查找,具体过程如下:

对于数组{2,7,11,15},查找的两个数的和是9,则初始化index1=1,index2=length-1=3。此时,分为三种情况:

  1. 若numbers[index1]+numbers[index2]>target,index2--
  2. 若numbers[index1]+numbers[index2]<target,index1++
  3. 相等,则返回

程序代码:

/**
	 * 找到两个下标,前提是数组numbers中正好就存在一组这样的解,这种方法只能针对有序表
	 * 
	 * @param numbers数组
	 * @param target目标值
	 * @return返回下标
	 */
	public static int[] twoSum_1(int[] numbers, int target) {
		int result[] = new int[2];// 用于返回最终的下标的数组
		int i = 0;// 第一个下标
		int j = numbers.length - 1;// 第二个下标
		while (i < j) {
			int tmp = numbers[i] + numbers[j];
			if (tmp == target) {
				result[0] = i + 1;
				result[1] = j + 1;
				break;// 跳出循环
			} else if (tmp > target) {
				j--;
			} else {
				i++;
			}
		}
		return result;
	}

时间复杂度为O(n)。

2.2无序数组

   对于无序数组,要找到两个数的下标,这样的对应关系,比较方便的办法是采用Hash表的存储结构,Hash表中的Key为数组中的值为数组中的值,Hash表中的Value的值为数组的index。在Hash表中key的值是不能重复的,若是数组中有相同的数,则会只保存后一个的value,则不影响问题的求解。

程序代码:

/**
	 * 找到两个下标,前提是数组numbers中正好就存在一组这样的解
	 * 
	 * @param numbers数组
	 * @param target目标值
	 * @return返回下标
	 */
	public static int[] twoSum_2(int[] numbers, int target) {
		int result[] = new int[2];// 用于返回最终的下标的数组
		int i = 0;
		int j = 0;
		HashMap<Integer, Integer> ht = new HashMap<Integer, Integer>();
		for (int m = 0; m < numbers.length; m++) {
			ht.put(numbers[m], m);
		}
		for (i = 0; i < numbers.length; i++) {
			int tmp = target - numbers[i];
			//存在这样的tmp
			if (ht.containsKey(tmp)) {
				j = ht.get(tmp);
				if (i != j){
					break;
				}else{
					continue;
				}
			}
		}
		//保存好下标
		result[0] = (i<j)?i:j;
		result[1] = i+j-result[0];
		result[0]++;
		result[1]++;
		return result;
	}

时间复杂度为O(n)。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏IT可乐

Java 集合详解

一、集合的由来   通常,我们的程序需要根据程序运行时才知道创建多少个对象。但若非程序运行,程序开发阶段,我们根本不知道到底需要多少个数量的对象,甚至不知道它的...

2729
来自专栏Golang语言社区

Go 语言数据类型

在 Go 编程语言中,数据类型用于声明函数和变量。 数据类型的出现是为了把数据分成所需内存大小不同的数据,编程的时候需要用大数据的时候才需要申请大内存,就可以充...

3187
来自专栏从流域到海域

《笨办法学Python》 第4课手记

《笨办法学Python》 第4课手记 这节课目的是让你掌握变量,跟C语言非常类似,很简单。 左边是变量名用”=”号给变量赋值。 不同的是我没有看到变量声明,作者...

1838
来自专栏用户2442861的专栏

Java中如何遍历Map对象的4种方法

既然java中的所有map都实现了Map接口,以下方法适用于任何map实现(HashMap, TreeMap, LinkedHashMap, Hashtabl...

1001
来自专栏CRPER折腾记

JS数组去重!!!一篇不怎么靠谱的"深度"水文

数组去重,这是一个老梗了...今天我又拿出来说了... 我们在考虑全面一点的情况下,数组去重的实现,比如针对NaN,undefined,{}; 这其中涉及的知识...

1034
来自专栏desperate633

LintCode 最小子数组 && 最大子数组题目分析代码最大子数组

判断加与不加的情况,这道题的解法很巧妙,类似于背包问题。 每个数组的元素都有两种情况,加与不加,所以我们从第一个元素开始判断,包括第一个元素时,和不包括第一个...

672
来自专栏电光石火

Java遍历Map对象的四种方式

关于java中遍历map具体哪四种方式,请看下文详解吧。 方式一 这是最常见的并且在大多数情况下也是最可取的遍历方式。在键值都需要时使用。 Map<I...

40110
来自专栏用户画像

7.2.1 直接插入排序

插入排序是一种简单直观的排序方法,其基本思想在于每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列,直到全部记录插入完成。

922
来自专栏一“技”之长

Swift讲解专题五——集合类型 原

        Swift中提供了3种集合类型,Array数据类型,Set集合类型,Dictionary字典类型。Array用于存放一组有序的数据,数据角标从0...

803
来自专栏Java大联盟

Java面试手册:集合框架

2293

扫码关注云+社区

领取腾讯云代金券