K数之和
描述
给定 N 个不同的整数数组和一个目标数字，在数组中找出相加等于这个数字的所有情况。
样例
int nums[] = { 10,20,30,40,50,60,70,80,90,100 };
输出：
[[100]
[90,10]
[80,20]
[70,30]
[20,70,10]
[60,40]
[30,60,10]
[40,50,10]
[30,50,20]
[20,30,40,10]]
思路：
没啥思路直接上dfs 暴力破解
#include <iostream>
#define GET_ARRAY_LEN(array,len){len=(sizeof(array)/sizeof(array[0]));}
using namespace std;
int res[100], k = 0, len, targer;
void sumOfKNumber(int* nums, int n, int sum) {
if (n <= 0 || sum < 0) return;
if (sum == 0) {
if (n < len && nums[n] == targer) {
cout << nums[n] << endl;
}
}
if (k > 0)
{
if (sum == nums[n - 1]) {
for (int i = k - 1; i >= 0; --i)
cout << res[i] << "+";
cout << nums[n - 1] << endl; // 输出时该元素还未加入数组
}
}
// 考虑取第几个数
res[k++] = nums[n - 1];
sumOfKNumber(nums, n - 1, sum - nums[n - 1]);
k--;
sumOfKNumber(nums, n - 1, sum);
}
int main()
{
int nums[] = { 10,20,30,40,50,60,70,80,90,100 };
targer = 100;
GET_ARRAY_LEN(nums, len);
sumOfKNumber(nums, len, targer);
}
应用
算法写出来当然是要有地方可以用，不然只为了刷题的话那将毫无意义。
封装成C# 代码 顺便优化了一下，不等于固定的数值而是寻找相近的值。
SumOfKNumber.cs
public class SumOfKNumber<T> where T : struct
{
private readonly List<decimal> _nums;
private readonly decimal _sum;
private readonly bool _lessThan;
public List<List<decimal>> NumList;
private readonly decimal[] _res;
private int k = 0;
private decimal _max = 0;
/// <summary>
/// 求最接近的那个值
/// </summary>
/// <param name="numEnums">数组</param>
/// <param name="sum">和为多少</param>
/// <param name="lessThan">是否小于这个和</param>
public SumOfKNumber(IEnumerable<T> numEnums, T sum, bool lessThan = false)
{
_nums = numEnums.Select(s => (decimal)(dynamic)s).ToList();
_sum = (decimal)(dynamic)sum;
_lessThan = lessThan;
_res = new Decimal[_nums.Count];
NumList = new List<List<decimal>>();
}
/// <summary>
/// 获取列表枚举
/// </summary>
/// <returns></returns>
public IEnumerable<IEnumerable<T>> GetNumList()
{
Sum(_nums, _nums.Count, (decimal)(dynamic)GetListMax());
return NumList.Select(s => s.Select(ss => (T)(dynamic)ss));
}
//获取最大值
private void Sum(IReadOnlyList<decimal> numEnums, int n, decimal sum)
{
if (n <= 0) return;
if (sum.Equals(0))
{
if (n < numEnums.Count && numEnums[n].Equals(_sum))
{
//Console.WriteLine(_sum + " = " + numEnums[n]);
NumList.Add(new List<decimal>() { numEnums[n] });
}
return;
}
if (k > 0)
{
if (sum.Equals(numEnums[n - 1]))
{
var list = new List<decimal>();
//Console.Write(_sum + " = ");
for (var i = k - 1; i >= 0; --i)
{
//Console.Write(_res[i] + "+");
list.Add(_res[i]);
}
list.Add(numEnums[n - 1]);
//Console.WriteLine(numEnums[n - 1]);
NumList.Add(list);
}
}
_res[k++] = numEnums[n - 1];
Sum(numEnums, n - 1, sum - numEnums[n - 1]);
k--;
// ReSharper disable once TailRecursiveCall
Sum(numEnums, n - 1, sum);
}
/// <summary>
/// 获取最大值
/// </summary>
/// <returns></returns>
public T GetListMax()
{
if (_max != 0)
{
return (T)(dynamic)_max;
}
HashSet<decimal> hashSet = new HashSet<decimal>() { 0 };
foreach (var num in _nums)
{
int count = hashSet.Count - 1;
var list = hashSet.ToArray();
for (int i = count; i >= 0; --i)
{
hashSet.Add(list[i] + num);
}
}
if (_lessThan)
{
// 小于等于 100
var enumerable = hashSet.ToList().Where(w => w <= _sum);
_max = enumerable.Max();
}
else
{
// 找最符合的那个数
var enumerable = hashSet.ToList();
enumerable.Sort();
decimal flag = Decimal.MaxValue;
foreach (var item in enumerable)
{
var abs = Math.Abs(_sum - item);
if (abs < flag)
{
flag = abs;
_max = item;
}
else
{
break;
}
}
}
return (T)(dynamic)_max;
}
}
使用：
class Program
{
static void Main(string[] args)
{
var nums = new List<float>() { 10, 10.2f, 20, 30, 40, 50, 60, 70, 80, 90, 100 };
Console.WriteLine("===========test1==========");
var test1 = new SumOfKNumber<float>(nums, 100.2f);
var max1 = test1.GetListMax();
var list1 = test1.GetNumList();
Print(list1, max1);
Console.WriteLine("===========test2==========");
var test2 = new SumOfKNumber<float>(nums, 100.2f, true);
var max2 = test2.GetListMax();
var list2 = test2.GetNumList();
Print(list2, max2);
}
static void Print<T>(IEnumerable<IEnumerable<T>> list, T max) where T : struct
{
foreach (var items in list)
{
var nums = items.ToList();
Console.Write(max + " = ");
for (int i = 0; i < nums.Count(); i++)
{
if (i == items.Count() - 1)
{
Console.Write(nums[i]);
}
else
{
Console.Write(nums[i] + "+");
}
}
Console.WriteLine();
}
}
}
应用场景
目前只想到了凑单。。。。。😅可能也是因为双十一刚过的原因吧。
