Addition of elements of an array to match the sum-CodePudding

How do I go about solving a problem in C# where I have an array and given a number I need to print the positions of elements whose sum is the given number.

int[] a = { 4,3,8,1}

Lets say I provide input number as 5 , then I achieve this by adding 4 1 . So the output should be [0,3] which is the position of element at 0th element and 3rd element.

I was trying to approach this taking each element in the for loop and running the second for loop with the remaining of elements which resulted in a very cumbersome code.

for(int i= 0; i< a.length; i  )
 { 
  // loop through remaining elements and check for sum
   for(..) 
    { 
    }      
 }

How to solve it using greedy technique or dynamic programming?

CodePudding user response：

You can do this in single loop (Complexity - O(n))

public int[] CheckSum(int[] nums, int target) {
    int[] sortedNums = new int[nums.Length];
        nums.CopyTo(sortedNums, 0);
        sortedNums = Array.Sort(nums);

        int left = 0, right = sortedNums.Length - 1;

        while (left < right)
        {
            if (sortedNums[left]   sortedNums[right] == target)
                break;

            if (sortedNums[left]   sortedNums[right] > target)
                right--;

            else if (sortedNums[left]   sortedNums[right] < target)
                left  ;
        }

        int leftIndex = Array.IndexOf(nums, sortedNums[left]);
        int rightIndex = Array.IndexOf(nums, sortedNums[right], leftIndex   1);

        if (rightIndex == -1)
            rightIndex = Array.IndexOf(nums, sortedNums[right], 0, leftIndex);

        return new int[] { leftIndex, rightIndex };
}

CodePudding user response：

Based on your question, with two loops:
You can try this:

using System;
using System.Collections.Generic;

public class Program
{
    public static void Main(string[] args)
    {
        int[] a = { 4,3,8,1,1,4};
        int input = int.Parse(Console.ReadLine());
        List<int> selectedNumbers = new List<int>();
        for(int i= 0; i< a.Length; i  )
        { 
            for(var j = 1; j<a.Length; j  ) 
            { 
                if(a[i]   a[j] == input)
                {
                    if(!selectedNumbers.Contains(i))
                        selectedNumbers.Add(i);
                    
                    if(!selectedNumbers.Contains(j))
                        selectedNumbers.Add(j);
                }
            }      
        }
        
        var outputArray = selectedNumbers.ToArray();
        for(int i= 0; i< outputArray.Length; i  )
        {
            Console.Write(selectedNumbers[i]   "\t");
        }
    }
}