using System;

using System.Linq;

using System.Collections.Generic;

using System.Text;

​

/*

​

**************** This is optimized Solution (UNDER CONSTRUCTION) *****************

​

Link: [https://www.scaler.com/academy/mentee-dashboard/class/26749/assignment/problems/157?navref=cl_tt_lst_nm]

Problem Description

​

Given an array of integers, find two numbers such that they add up to a specific target number.

​

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 < index2. Please note that your returned answers (both index1 and index2 ) are not zero-based. Put both these numbers in order in an array and return the array from your function ( Looking at the function signature will make things clearer ). Note that, if no pair exists, return empty list.

​

If multiple solutions exist, output the one where index2 is minimum. If there are multiple solutions with the minimum index2, choose the one with minimum index1 out of them.

​

Input: [2, 7, 11, 15], target=9

Output: index1 = 1, index2 = 2

*/

​

public class Program

{

    private static List<int> twoSum(List<int> A, int B)

    {

        int _arrCount = A.Count; 

        List<int> _indices = new List<int>();

        Dictionary<int, int> _indicesDict = new Dictionary<int, int>();

        for(var i = 0; i < _arrCount; i++){

            if(!_indicesDict.ContainsKey(A[i])){

                _indicesDict.Add(i, A[i]);

            }

        }

        for(var j = 0; j < _indicesDict.Count; j++){

            var _currKeyValPair = _indicesDict.ElementAt(j);

            int _targetNum = B - _currKeyValPair.Value;

            if(_indicesDict.ContainsValue(_targetNum)){

                 if(_indices.Count > 0){

                     if(_indicesDict[_targetNum] < _indices[1] - 1 && _indicesDict[_targetNum] > _currKeyValPair.Value){

                            _indices[0] = _currKeyValPair.Value + 1;

                            _indices[1] = _indicesDict[_targetNum] + 1;

                        }

                 }else{

                     _indices.Add(_currKeyValPair.Key + 1);

                    _indices.Add(_indicesDict.FirstOrDefault(x => x.Value == _targetNum).Key + 1);

                 }

            }

        }

        return _indices;

    }

    public static void Main()

    {

        List<int> _HashingSum = new List<int>(){ 1, 1, 1 };

        int _target = 2;

        //List<int> _HashingSum = new List<int>(){ -5, 1, 4, -7, 10, -7, 0, 7, 3, 0, -2, -5, -3, -6, 4, -7, -8, 0, 4, 9, 4, 1, -8, -6, -6, 0, -9, 5, 3, -9, -5, -9, 6, 3, 8, -10, 1, -2, 2, 1, -9, 2, -3, 9, 9, -10, 0, -9, -2, 7, 0, -4, -3, 1, 6, -3 };

        //int _target = -1;

        //List<int> _HashingSum = new List<int>(){ 4, 7, -4, 2, 2, 2, 3, -5, -3, 9, -4, 9, -7, 7, -1, 9, 9, 4, 1, -4, -2, 3, -3, -5, 4, -7, 7, 9, -4, 4, -8 };

        //int _target = -3;

        //List<int> _HashingSum = new List<int>(){ 2, 7, 11, 15 };

        //List<int> _HashingSum = new List<int>(){ 2, 1, 7, 7, 2 };

        //List<int> _HashingSum = new List<int>(){ 1, 2, 3 };

        //int _target = 9;

        List<int> isSumExist = Program.twoSum(_HashingSum, _target);

        Console.WriteLine("The Target sum Indices are: " + string.Join(" ", isSumExist));

    }

}