【題目描述】
Given n unique integers, number k (1<=k<=n) and target.
Find all possible k integers where their sum is target.
給定n個不同的正整數(shù)，整數(shù)k（1<=?k <= n）以及一個目標數(shù)字。
在這n個數(shù)里面找出K個數(shù)煤杀，使得這K個數(shù)的和等于目標數(shù)字树绩，你需要找出所有滿足要求的方案。
【題目鏈接】
www.lintcode.com/en/problem/k-sum-ii/
【題目解析】
此題與Lintcode89類似拌阴。只是整數(shù)k的取值不同。
找兩數(shù)之和是否為target,可以使用遍歷。先來看看兩數(shù)之和為target所對應(yīng)的判斷條件—— xi+xj=targetx_i + x_j = targetxi+xj=target, 可進一步轉(zhuǎn)化為 xi=target?xjx_i = target - x_jxi=target?xj, 其中 iii 和 jjj 為數(shù)組中的下標因篇。推理后便可將找兩數(shù)之和轉(zhuǎn)化為了找一個數(shù)是否在數(shù)組中。
基本思路有了笔横，現(xiàn)在就來看看怎么實現(xiàn)竞滓，顯然需要額外的空間(哈希表)來保存已經(jīng)處理過的 xjx_jxj(注意這里并不能先初始化哈希表，否則無法排除兩個相同的元素相加為target 的情況), 如果不滿足等式條件吹缔，那么我們就往后遍歷商佑，并把之前的元素加入到哈希表中，如果target減去當前索引后的值在哈希表中找到了厢塘，那么就將哈希表中相應(yīng)的索引返回即可茶没。
【參考答案】
