Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created September 21, 2017 18:29
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/6443b454620bf732fe940720de6a9d1b to your computer and use it in GitHub Desktop.
Save jianminchen/6443b454620bf732fe940720de6a9d1b to your computer and use it in GitHub Desktop.
Look into C# Array.IndexOf approach and see how it works - a few issues to look into
using System;
using System.Collections.Generic;
class Solution
{
public static int[] GetIndicesOfItemWeights(int[] arr, int limit)
{
// your code goes here
if(arr == null || arr.Length == 0)
{
return new int[0]; // empty array
}
// assume that the array is not empty
var set = new HashSet<int>(); // O(n)
var length = arr.Length;
for(int index = 0; index < length; index++)
{
var visit = arr[index]; // 4, 6, 10, 15
var search = limit - visit; // 17, 15, 11, 6
if(set.Contains(search)) // true
{
return new int[]{index, Array.LastIndexOf(arr, search)}; // 15, 6 [3, 1]
}
set.Add(visit); // 4, 6 , 10,
}
return new int[0];
}
static void Main(string[] args)
{
var result = GetIndicesOfItemWeights(new int[]{4, 6, 10,15,16}, 21);
foreach(var item in result)
{
Console.WriteLine(item);
}
}
}
// 3 - 15, 1 - 6, 15 + 6 = 21
// two items ->
// sorted array -> O(nlogn)
// n(n-1) -> O(n^2)
// brute force
// for(int first = 0; first < length - 1; first ++)
// for(int second = first + 1; second < length; second++)
// sum = arr[first] + arr[second]
// return new int[]{first, second}
// Array.Sort(arr) -> ascending order
// two pointers 4, 16 -> 20 < 21, -> 6 + 16 = 22, 6 + 15
// O(n)
// data search ->
// extra ->
// 4, 17 in hashset -> Dictionary<int, int>, value, index
// <4, 0>,
// 6 -> 15 , add <6, 1> to the table
// when we find 4, 21-4 = 17.
// Array.IndexOf(value) -> first occurrence -> hashtable -> hashset -> data search
@jianminchen
Copy link
Author

Things to look into:
Array.Sort -> I tried to write arr.Sort, so I need to look into Abstract class Array and the API Sort is defined.

Read c# Array -
Read 10 minutes - C# Arrays Tutorial
https://msdn.microsoft.com/en-us/library/aa288453(v=vs.71).aspx

20 minutes reading:
http://www.c-sharpcorner.com/article/working-with-arrays-in-C-Sharp/

Study stackoverflow posts related to C# Array -

More reading:
https://www.codeproject.com/Articles/6118/All-about-abstract-classes

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment