Algorithm that finds two numbers that sum to a target

Question

Is this the optimal algorithm to satisfy this problem?

It does work. I get the: 1 and 5 (or 5 and 1) as 1 + 9 = 10.

---

Here's a function that, when passed a list and a target sum, returns two distinct zero-based indices of any two of the numbers, whose sum is equal to the target sum. If there are no two numbers, the function should return null.

For example, FindTwoSum(new List() { 3, 1, 5, 7, 5, 9 }, 10) should return a Tuple containing any of the following pairs of indices:

• 0 and 3 (or 3 and 0) as 3 + 7 = 10
• 1 and 5 (or 5 and 1) as 1 + 9 = 10
• 2 and 4 (or 4 and 2) as 5 + 5 = 10

---

Someone had suggested the following, but I was not sure how to code it.

Order the data. Start at the left and the right at the same time. Add the left most and the right most entries. If the total is too high, move from the right towards the center. If the total is too low, move from the left towards the center.

So I came up with the following. It has 3 loop constructs though.

---

namespace AlgorithmFind2Sum
{
    class TwoSum
    {
        public static void Main(string[] args)
        {
            // This set of data will find a match that adds up to the sum.
            Tuple<int, int> indices = FindTwoSum(new List<int>() { 3, 1, 5, 7, 5, 9 }, 10);

            // This set of data will NOT find a match that adds up to the sum.
            //Tuple<int, int> indices = FindTwoSum(new List<int>() { 1, 2, 4, 5, 7, 7 }, 10);

            if (indices != null)
            {
                // Write.
                Console.WriteLine("Entry that added up to the sum: " + indices.Item1 + " " + indices.Item2);

                // Reads the next line.
                Console.ReadLine();
            }
            else
            {
                // Write.
                Console.WriteLine("None added up to the sum.");

                // Reads the next line.
                Console.ReadLine();
            }
        }

        public static Tuple<int, int> FindTwoSum(IList<int> list, int sum)
        {
            //++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
            // Order the data - sort it.
            //++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

            // Using LINQ OrderBy method (it will generate new List<int> with items sorted):
            var orderedList = list.OrderBy(x => x).ToList();

            string finished = "N";
            string found = "N";
            string firstOuterLoopEntry = "Y";
            int outerLoopCount = 0;
            int innerLoopCount = 0;
            int loopUpperBound = list.Count - 1;
            int SumOfTwo = 0;

            // Loops as long as the condition is true.
            while (finished == "N")
            {
                while (outerLoopCount < orderedList.Count)
                {
                    innerLoopCount = 0;

                    while (innerLoopCount < loopUpperBound)
                    {
                        if (firstOuterLoopEntry == "Y")
                        {
                            SumOfTwo = orderedList[outerLoopCount] + orderedList[innerLoopCount + 1];

                            if (SumOfTwo == sum)
                            {
                                found = "Y";
                                break;
                            }
                        }
                        else
                        {
                            // Set the loop upper bound here again in that I have to make up for skipping the entry that is itself.
                            loopUpperBound = orderedList.Count;

                            // Do not process the entry that is itself.
                            if (innerLoopCount != outerLoopCount)
                            {
                                SumOfTwo = orderedList[outerLoopCount] + orderedList[innerLoopCount];

                                if (SumOfTwo == sum)
                                {
                                    found = "Y";
                                    break;
                                }
                            }
                        }

                        innerLoopCount = innerLoopCount + 1;
                    }

                    if (found == "Y")
                    {
                        finished = "Y";
                        break;
                    }
                    else
                    {
                        firstOuterLoopEntry = "N";

                        outerLoopCount = outerLoopCount + 1;
                    }
                }

                finished = "Y";
            }

            // Return.
            if (found == "Y")
            {
                return Tuple.Create(orderedList[outerLoopCount], orderedList[innerLoopCount + 1]);
            }
            else
            {
                return null;
            }
        }
    }
}

Answer 1

You sort but don't use the sort. Not getting why you need to reset loopUpperBound = orderedList.Count; Just start with that. Don't use Y N - use a Boolean. You are potentially evaluating each pair twice.

It is pretty simple:

public static Tuple<int, int> GetPair(List<int> ints, int sum)
{
    int upperIndex = ints.Count - 1;
    int lowerIndex = 0;
    ints.Sort();
    while (lowerIndex < upperIndex)
    {
        int curSum = ints[lowerIndex] + ints[upperIndex];
        if (curSum == sum)
        {
            return new Tuple<int, int>(ints[lowerIndex], ints[upperIndex]);
        }
        if (curSum < sum)
        {
            lowerIndex++;
        }
        else
        {
            upperIndex--;
        }
    }
    return null;
}

If you want to brute force it:

public static Tuple<int, int> GetPairBrute(List<int> ints, int sum)
{
    for (int i = 0; i < ints.Count - 1; i++)
    {
        for (int j = i + 1; j < ints.Count; j++)
        {
            if (ints[i] + ints[j] == sum)
            {
                return new Tuple<int, int>(ints[i], ints[j]);
            }
        }
    }
    return null;
}