第一题：两数之和[四种编程，三种解法]

题目难度：简单

题目类型：数组

获得收货： 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]

（3）nums[start]+nums[end]=target，返回结果；

最后在拷贝数组中找到满足条件的两个原始的下标；

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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 elem) j--;
            //如果while没有i target) end--;
            else break;
        }
        int k=0;
        for(int i=0;i=result[1])
            System.out.println("数组中没有两个数之和等于target!");
        else{
            for(int i:result)
            {
                System.out.print(i); 

                System.out.print(" ");
            }
        }

    }
}

C++实现：

参考大神们方法，采用哈希法思想，key为nums数组中的元素，val为数组中的元素在数组中的下标；num2=target-num1,如果num2在map中存在，则返回num1和num2在数组中的索引；

//#include 
#include 
#include 
#include 
using namespace std;
class Solution{
public:
    vector towSum(vector nums,int target){
        vector result;
        map elemIndex;
        int len=nums.size();
        for(int i=0;i(nums[i],i));
        }
        return result;
    }
};
int main()
{
    cout<<"请输入数组个数以及数组元素，以空格隔开："<>n;
    vector nums(n);
    for(int i=0;i>nums[i];
    }
    cout<<"请输入target:"<>target;
    Solution sol = Solution();
    vector result=sol.towSum(nums,target);
    vector::iterator ite=result.begin();
    for(;ite != result.end();ite++)
        cout<<*ite<<" ";
    cout< 
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._


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)
  }
}
 
感悟： 
感觉编程语言长时间不练习，再次拾起来需要查找的方法还挺多，最后，哪有什么不足之处，希望各位朋友多多留言，给出你们宝贵的建议，我们一次成长，谢谢了！
 同时，也欢迎大家关注我的微信公众号：算法小金子；

第一题：两数之和[四种编程，三种解法]

Python相关栏目本月热门文章