C# FindTwoSum

[thelittleguy]

Θα ήθελα την βοήθειά σας στην επίλυση του παρακάτω.

 

Εκφώνηση

 

Write a function that, given a list and a target sum, returns zero-based indices of any two distinct elements whose sum is equal to the target sum. If there are no such elements, the function should return null.

For example, FindTwoSum(new List<int>() { 1, 3, 5, 7, 9 }, 12) should return any of the following tuples of indices:

• 1, 4 (3 + 9 = 12)
• 2, 3 (5 + 7 = 12)
• 3, 2 (7 + 5 = 12)
• 4, 1 (9 + 3 = 12)

 

Κώδικας που δόθηκε.

 

using System;

using System.Collections.Generic;

 

class TwoSum

{

    public static Tuple<int, int> FindTwoSum(IList<int> list, int sum)

    {

        throw new NotImplementedException("Waiting to be implemented.");

    }

 

    public static void Main(string[] args)

    {

        Tuple<int, int> indices = FindTwoSum(new List<int>() { 1, 3, 5, 7, 9 }, 12);

        Console.WriteLine(indices.Item1 + " " + indices.Item2);

    }

}

 

Μπορεί κάποιος να με βοηθήσει να το λύσω? 

 

[παπι]

Τσεκαρεις το πρώτο με το δεύτερο κάνει 12? Όχι το πρώτο με το τρίτο; Όχι... Το 2 με 3? Όχι...

[albNik]

Το Tuple επιστρέφει ενα ζευγαρι, θες λιστα απο Tuple, List<Tuple<int,int>> 

for(i=0;i<list.Count;i++)
  for(j=i+1; j<list.Count;j++)
    if(list[i]+list[j]==sum)
      result.Add(new Tuple(i,j));

[παπι]

Δώσε κάνα αεροπλανικο τουλάχιστον....

[MeTaXaS4]

 

Το Tuple επιστρέφει ενα ζευγαρι, θες λιστα απο Tuple, List<Tuple<int,int>> 

for(i=0;i<list.Count;i++)
  for(j=i+1; j<list.Count;j++)
    if(list[i]+list[j]==sum)
      result.Add(new Tuple(i,j));

 

δεν θέλει λίστα, θέλει 1 ζευγάρι που κάνει match το ζητούμενο.

[Papakaliati]

returns zero-based indices of any two distinct elements whose sum is equal to the target sum.

 

indices of any two. Aρα τα ζηταει ολα, οχι μονο ενα. Και με tuple μπορεις να επιστρεψεις ενα μονο ζευγαρι. Eπιπλεον εχει και παραδειγμα μετα που τα επιστρεφει ολα. 

[defacer]

Το any two είναι 100% ξεκάθαρο πως σημαίνει ένα οποιοδήποτε ζευγάρι μας κάνει, η εκφώνηση ως έχει δε ζητάει να βρεθούν όλα. Αν ήθελε θα έπρεπε να πει all distinct pairs ή κάτι ανάλογο.

 

That said το πρόβλημα είναι βέβαια μια απλοποιημένη υποπερίπτωση του subset sum, οποιαδήποτε half decent λύση θα μπορέσει να τα βρει όλα με πρακτικά μηδέν διαφορά από το να βρει μόνο ένα (απλά αφήνεις τον αλγόριθμο να συνεχίσει αφότου βρει τη πρώτη λύση).

 

Μια καλή προσέγγιση είναι:

 

1. Sort

2. For each N

3. Binary search στο sorted πίνακα να βρούμε τον αριθμό M = S - N όπου S το επιθυμητό άθροισμα

4. Αν υπάρχει (και δεν είναι το ίδιο index με το N που εξετάζουμε) βρήκαμε μια λύση

 

κλπ