4

I want to create a method to find the index of two numbers whose sum is target.

So, I have created this method:

public static int[] TwoSum(int[] nums, int target)
{
    for (var i = 0; i < nums.Length; i++)
    {
        for (var j = 0; j < nums.Length; j++)
        {
            if (j == i) continue;

            if (nums[i] + nums[j] == target)
            {
                return new[] { i, j };
            }
        }
    }
}

Which works fine. However, I am trying to learn myself some LINQ and can't figure it out. I looked at various examples, but I always end up stuck because I am using the same array twice. So I don't know what to select and how to access it twice while also making sure it doesn't go through the same indexes twice.

Any help getting a LINQ from the above loops would be appreciated.

Sample data:

var nums = new [] { 2, 7, 11, 15 };
var target = 9;
Improve this question
2
  • Added to main question @D-Shih Commented Aug 11, 2018 at 20:40
  • Ok I saw it thanks Commented Aug 11, 2018 at 20:41

4 Answers 4

Reset to default
3

The LINQ equivalent of your loop would be:

from x in nums.Select((n, i) => new { Number = n, Index = i })
from y in nums.Select((n, i) => new { Number = n, Index = i })
where x.Index != y.Index && x.Number + y.Number == target
select new [] { x.Index, y.Index }

But this requires the creation of anonymous type instance so I would say the loop version is much better and efficient.

Improve this answer
Sign up to request clarification or add additional context in comments.

9 Comments

Great solution!
It looks nice, indeed! I have a question which may seem noobish. How would the code look like in "C# version of LINQ"?
Please check C# code sample and output. dotnetfiddle.net/EXc0ES
@csharpbd I was referring to replacing the from and where to C# methods Select, Where etc.
@user9248102 you can take a look at this answer for that. Most of the time query syntax is more readable and I prefer that but for inner loops like in this case I think query syntax looks better.
|
2

Here it is as a single LINQ statement, using SelectMany. With LINQ, you have to flip your mind upside down... just type return and then go from there.

public static int[] TwoSumWithLinq(int[] nums, int target)
{
    return nums.SelectMany
    (
        (m, i) => nums.Select
            (
                (n,j) => new { n, m, i, j }
            )
    )
    .Where
    (
        r => (r.i != r.j) && (r.m + r.n == target)
    )
    .Select
    (
        r => new int[] { r.i, r.j }
    )
    .FirstOrDefault();
}

Link to working example on DotNetFiddle

Improve this answer

1 Comment

Pretty clean solution
1

I would go with the slightly cleaner version:

public static int[] TwoSum(int[] nums, int target)
{
    return
    (
        from i in Enumerable.Range(0, nums.Length)
        from j in Enumerable.Range(0, nums.Length)
        where i != j && nums[i] + nums[j] == target
        select new [] { i, j }
    ).FirstOrDefault();
 }
Improve this answer

6 Comments

Time complexity of this solution is O(N^4), why would you evaluate Enumerable.Range(0, nums.Length) twice
@MrinalKamboj - It's an array - .Length is O(1).
looping is done in the Enumerable.Range not nums.Length, which in itself part of another outer Enumeration.
@MrinalKamboj - Yes, but that would make it only O(N^2). Why do you say it is O(N^4)?
from i in Enumerable.Range(0, nums.Length) would be O(N^2), since you are not materializing the collection, it would be multiple enumeration. In my understanding Enumerable.Range(0, nums.Length) shall be materialized before its used in the Linq query
|
-1 
public static int[] TwoSum(int[] nums, int target)
{
    int[] indexes = Enumerable.Range(0, nums.Length).ToArray();

    var result =  from i in indexes
                  from j in indexes
                  where i != j && (nums[i] + nums[j]) == target
                  select new []
                  {
                      i,
                      j
                  };

    return result.FirstOrDefault();
}

Please note that the method will return null if there aren't any members in the array that will match the condition (sum of members = target)

Improve this answer

1 Comment

I am not down-voter, but your solution would have much higher time complexity, for higher values of N would tend to be slower, moreover when overload of Select / SelectMany provides the index, then its more elegant to use

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.