如何在linq中使用where子句和sum子句

本文关键字：子句 where sum linq | 更新日期: 2023-09-27 18:14:50

我想从价格表中得到一个值的总和等于我想要的值的列表。让我举例说明。

List<int> prices= new List{ 1, 2, 3, 4, 5 };
List<int> filteredList = GetSumList(4); // get list where the sum equals to 4, 1-3 or just 4. it doesn't matter which one.

如何编写GetSumList(int sum)函数

如何在linq中使用where子句和sum子句

如果请求的sum不是那么大;和所有项都是正的(允许为零)，并且您不太介意内存，您可以使用以下方法:

public static IEnumerable<int> GetSumList(this IEnumerable<int> values, int sum) {
    List<int>[] sets = new List<int>[sum+1];
    sets[0] = new List<int>();
    foreach(int xi in values) { //O(N*sum*N) with N the number of items
        List<int> f0, f1, f2;
        for(int i = sum-xi; i >= 0; i--) { //O(N*sum)
            f0 = sets[i];
            f1 = sets[i+xi];
            if(f0 != null && (f1 == null || f0.Count < f1.Count-1)) {
                f2 = new List<int>(f0);//make clone, O(N)
                f2.Add(xi);
                sets[i+xi] = f2;
            }
        }
    }
    return sets[sum];
}

(如果不存在，则返回null;此算法还将返回最小的子集(如果有的话)。

该算法利用动态规划，考虑集合的列表。每个都有一个不同的和。如果在计算临时值时使用链表而不是List<int> s，则可以更快一点，因为这允许(共享)克隆和在头0(1)中插入。

Demo(使用csharp交互shell):

csharp> List<int> prices= new List<int>(new int[] { 1, 2, 3, 4, 5 }); 
csharp> prices.GetSumList(4);                                                              
{ 4 }
csharp> prices.GetSumList(6); 
{ 2, 4 }
csharp> prices.GetSumList(7); 
{ 3, 4 }
csharp> prices.GetSumList(8); 
{ 3, 5 }
csharp> prices.GetSumList(9); 
{ 4, 5 }
csharp> prices.GetSumList(10);
{ 2, 3, 5 }
csharp> prices.GetSumList(11); 
{ 2, 4, 5 }
csharp> prices.GetSumList(12); 
{ 3, 4, 5 }
csharp> prices.GetSumList(13); 
{ 1, 3, 4, 5 }
csharp> prices.GetSumList(14); 
{ 2, 3, 4, 5 }
csharp> prices.GetSumList(15); 
{ 1, 2, 3, 4, 5 }
csharp> prices.GetSumList(16); 
null

如果你有列表的列表，你可以做一个非常简单的LINQ扩展方法，像这样

using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;

public class Test
{
    public static void Main()
    {
        var lists = new List<List<int>>
        {
            new List<int> { 1, 2, 3 }, // 6
            new List<int> { 3 }, // 3
            new List<int> { 3, 3 }, // 6
            new List<int> { 1, 2 }, // 3
            new List<int> { 6 } // 6
        };
        Console.WriteLine(lists.GetSumList(6).Count); // 3
    }
}
public static class ListHelpers
{
    public static List<List<int>> GetSumList(this List<List<int>> list, int sum)
    {
        return list.Where(x => x.Sum() == sum).ToList();
    }
}
相关文章：