Annettuna on lista, jossa on n lukua, sekä luku x. Monellako tavalla voidaan muodostaa lukupari, jossa on kahdessa eri kohdassa listassa oleva luku ja jonka summa on enintään x?

Voit olettaa, että n on enintään 10^5 ja jokainen listan luku ja x on kokonaisluku välillä 1 \dots 10^9. Tavoitteena on, että algoritmin aikavaativuus on O(n \log n).

Python

Toteuta tiedostoon twosum.py funktio find, joka ilmoittaa lukuparien määrän.

def find(t,x):
    # TODO

if __name__ == "__main__":
    print(find([1,2,3],4)) # 2
    print(find([5,2,4,7],10)) # 4
    print(find([1,1,1,1],2)) # 6
    print(find([1,1,1,1],1)) # 0
    print(find([8,8,1,2,5,1,9,3],9)) # 14

Java

Toteuta tiedostoon TwoSum.java metodi find, joka ilmoittaa lukuparien määrän.

public class TwoSum {
    public long find(int[] t, int x) {
        // TODO
    }

    public static void main(String[] args) {
        TwoSum t = new TwoSum();
        System.out.println(t.find(new int[] {1,2,3}, 4)); // 2
        System.out.println(t.find(new int[] {5,2,4,7}, 10)); // 4
        System.out.println(t.find(new int[] {1,1,1,1}, 2)); // 6
        System.out.println(t.find(new int[] {1,1,1,1}, 1)); // 0
        System.out.println(t.find(new int[] {8,8,1,2,5,1,9,3}, 9)); // 14
    }
}