题目难度：简单
题目类型：数组
获得收货： java、C++、Python、Scala编程知识、两数之和解题思想、快排算法；
解题流程：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现(重点)。
你可以按任意顺序返回答案。
示例一：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]
示例二：
输入：nums = [3,2,4], target = 6
输出：[1,2]
提示：
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案
Java实现：
本文采用快排算法(每次将一个元素放在正确位置)；
首先，将原数组拷贝一份，即numsBak，然后 对数组nums进行排序(可以采用快排、归并等排序算法)，然后对排好序的数组使用两个指针start和end向中间夹击，分三种情况：
（1）nums[start]+nums[end]>target，end减1；
（2）nums[start]+nums[end]<target，start加1；
（3）nums[start]+nums[end]=target，返回结果；
最后在拷贝数组中找到满足条件的两个原始的下标；
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**基本知识
* 在java中如果是基本类型(int、String等)，则实参不会改变(值传递)；
如果是对象(集合：Map、数组等)，则实参会改变(传的是引用)；*/
public class Solution {
//快排算法
public void quickSort(int[] nums,int low,int high) {
int i=low, j=high;
if(i>=j)
return; //如果没有此判断会一一直递归，然后报栈溢出，
int elem = nums[low]; //不能放第一行，否则排好序退出时会导致ArrayIndexOutOfBoundsException
//经过一次快排，都会将一个元素放在正确位置，其左边元素比其小，右边元素比其大；
while(i<j){
while(i<j && nums[j] > elem) j--;
//如果while没有i<j,可能导致j--,出现nums[j]ArrayIndexOutOfBoundsException；
if(i<j) nums[i] = nums[j];
while(i<j && nums[i]<= elem) i++;
if(i<j) nums[j] = nums[i];
}
nums[i] = elem;
quickSort(nums,low,i-1);
quickSort(nums,i+1,high);
}
//解题方法
public int [] twoSum(int[] nums,int target){
int[] result = new int[2];
int[] numBak = new int[nums.length]; //用于找到两数之和初始数组中的下标
System.arraycopy(nums,0,numBak,0,nums.length);
quickSort(nums,0,nums.length-1);
//找到等于target的两个数在排好序的数组中的下标；
int start=0,end=nums.length-1;
while(start < end){
int curVal =nums[start] + nums[end];
if(curVal < target) start++;
else if(curVal > target) end--;
else break;
}
int k=0;
for(int i=0;i<numBak.length;i++){
if(numBak[i] == nums[start] || numBak[i] == nums[end]){
result[k++] = i;
}
}
return result;
}
public static void main(String[] args){
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
/**java.io.BufferedReader类readLine()方法读取一行数据，必须捕获异常*/
//读入数据
System.out.println("请输入数组元素和target值，以单空格分割,输入完后按enter键：");
String line = null;
try{
line =br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
String[] numsStr = line.split(" ");
int target=0;
int[] nums = new int[numsStr.length-1];
for(int i=0;i<numsStr.length;i++){ //
if(i<numsStr.length-1)
nums[i] = Integer.parseInt(numsStr[i]);
else
target = Integer.parseInt(numsStr[i]);
}
//方法调用
Solution sol= new Solution();
int[] result= sol.twoSum(nums,target);
if(result[0]>=result[1])
System.out.println("数组中没有两个数之和等于target!");
else{
for(int i:result)
{
System.out.print(i);
System.out.print(" ");
}
}
}
}
/**测试用来：
123 2 3 45 5 2313 8
123 23 4 54 21 24 15 38
5 32 2 4 5 12 10
13 2 43 5 8
*/
C++实现：
参考大神们方法，采用哈希法思想，key为nums数组中的元素，val为数组中的元素在数组中的下标；num2=target-num1,如果num2在map中存在，则返回num1和num2在数组中的索引；
//#include <bits/stdc++.h>
#include <vector>
#include <map>
#include <iostream>
using namespace std;
class Solution{
public:
vector<int> towSum(vector<int> nums,int target){
vector<int> result;
map<int,int> elemIndex;
int len=nums.size();
for(int i=0;i<nums.size();i++)
{
int num2=target-nums[i];
if(elemIndex.count(num2)==1){
int j=elemIndex[num2];
if(i<j)
{
result.push_back(i);
result.push_back(j);
}else{
result.push_back(j);
result.push_back(i);
}
break;
}
elemIndex.insert(pair<int,int>(nums[i],i));
}
return result;
}
};
int main()
{
cout<<"请输入数组个数以及数组元素，以空格隔开："<<endl;
int n=0;
cin>>n;
vector<int> nums(n);
for(int i=0;i<n;i++){
cin>>nums[i];
}
cout<<"请输入target:"<<endl;
int target;
cin>>target;
Solution sol = Solution();
vector<int> result=sol.towSum(nums,target);
vector<int>::iterator ite=result.begin();
for(;ite != result.end();ite++)
cout<<*ite<<" ";
cout<<endl;
system("pause");
return 0;
}
Python实现：
参考大神们方法，与哈希方法类似，对数组遍历一次，使用数组temp保存剩余未遍历的元素；num2=target-nums[i];如果num2在temp中出现，则找到，并结束循环；
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
numLen =len(nums)
j=-1
for i in range(1,numLen):
temp = nums[i:]
num2 = target - nums[i]
if num2 in temp:
j=nums.index(num2)
break
if j>=0:
return [i,j]
else:
return []
if __name__ == "__main__":
line = input("请输入数组元素，以空格隔开，然后按enter键：\n")
strList = line.split(' ')
target= input("请输入target,然后按tab键：\n")
nums = [int(elem) for elem in strList] #python的特有写法，对list遍历，然存储；
#nums = list(map(int, strList)) #实现上面语句的效果
sol = Solution()
result = sol.twoSum(nums,int(target))
for i in result:
print(str(i) + " ")
#测试用例：12 32 3 43 413 13
Scala实现：
参考大神们方法，本身上也是采用Hash的方法实现的；可以和C++、Python版本进行对比；
import io.StdIn._
/**
*Scala 函数式编程
* val声明的变量不可变的
* var声明的变量是可变的；
* 在Scala中函数无法对传入的参数进行改变；
*/
object Solutions {
def twoSum(nums:Array[Int],target:Int):Array[Int] ={
var valIndex:Map[Int,Int] = Map()
for(i <- nums.indices){
if( valIndex.contains(target-nums(i))) return Array(valIndex(target-nums(i)),i)
valIndex += (nums(i) -> i)
}
return Array()
}
def main(args: Array[String]): Unit = {
val str:String = readLine("请输入数组元素和target,以空格隔开，然后按enter：\n")
val numsTarget:Array[Int] = str.split(' ').map(_.toInt)
val nums:Array[Int] = numsTarget.take(numsTarget.length-1)
val target:Int = numsTarget(numsTarget.length-1)
val result:Array[Int] = twoSum(nums,target)
result.foreach(println)
}
}
感悟：
感觉编程语言长时间不练习，再次拾起来需要查找的方法还挺多，最后，哪有什么不足之处，希望各位朋友多多留言，给出你们宝贵的建议，我们一次成长，谢谢了！
同时，也欢迎大家关注我的微信公众号：算法小金子；
